c++ 启发式搜索解决数字华容道问题（N数码问题）
本帖最后由 这个显卡不太冷 于 2020-9-24 20:42 编辑好的。
原因是上实验课太无聊了，教室的电脑是Windows7，还有小工具可以玩。
里面有个自带的华容道游戏，就是数字华容道。
玩法就是把所有数字按升序排列。
由于太蠢了，并不会玩，遂写了个暴力来搜解法。
用A*实现的，启发函数就是所有数字距离它位置的曼哈顿距离。
4*4的大概需要3G的空间可以搜出答案。速度倒是还能接受。
```cpp
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
int n = 4;
unordered_map<string, int> dist;
unordered_map<string, pair<string, char> > pre;
typedef pair<int, string> PIS;
int f(string s)
{
int res = 0;
for(int i = 0; i < s.size(); i++)
{
if(s == 'x') continue;
int t = s - 1;
res += abs(i / n - t / n) + abs(i % n - t % n);
}
return res;
}
void out(string s)
{
for(char x:s) cout << (int)x << ' '; cout << endl;
}
string bfs(string st)
{
string ed = "";
for(int i = 1; i < n * n; i++) ed += (char)i; ed += 'x';
int dir = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
char op = "udlr";
priority_queue<PIS, vector<PIS>, greater<PIS> > q;
q.push({f(st), st});
dist = 0;
while(q.size())
{
auto t = q.top(); q.pop();
string state = t.second;
// out(state);
if(state == ed) break;
int step = dist;
int x, y;
for(int i = 0; i < state.size(); i++)
if(state == 'x')
{
x = i / n, y = i % n;
break;
}
string src = state;
for(int i = 0; i < 4; i++)
{
int dx = x + dir, dy = y + dir;
if(dx < 0 || dy < 0 || dx >= n || dy >= n) continue;
// src = state;
swap(src, src);
if(!dist.count(src) || dist > step + 1)
{
dist = step + 1;
pair<string, int> o = {state, op};
q.push({step + 1 + f(src), src});
pre = o;
}
swap(src, src);
}
}
string res = "";
while(ed != st)
{
auto o = pre;
res += o.second;
ed = o.first;
}
reverse(res.begin(), res.end());
return res;
}
main()
{
string x, st;
for(int i = 1; i <= n * n; i++)
{
cin >> x;
if(x == "x") st += x;
else st += (char)stoi(x);
}
cout << bfs(st);
}
/*
1 8 3 6 11 7 15 9 4 x 12 2 10 14 5 13
1 2 3 4 5 6 7 8 9 10 11 12 13 14 x 15
x 7 11 5 15 3 9 6 1 2 12 14 10 13 4 8
*/
```
用法就是直接输入数字的排列。空格用 `x` 代替。
随便在4399找了个试试。
!(data/attachment/forum/202009/24/185755y0ffg6ay6hc2gc76.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
!(data/attachment/forum/202009/24/185943f3500c86coj88g6t.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
!(data/attachment/forum/202009/24/185949l2x8wm2zr2k224rc.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
(data/attachment/forum/?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "3.exe")
也给一个编译好的文件吧。
markdown 编辑器居然不能插入附件
http://www.4399.com/flash/196034_2.htm
附上一个游戏地址 顶 {:05:} 发个视频上来吧 nkc3g4 发表于 2020-9-29 19:21
发个视频上来吧
这周没有实验课了。只有上次录这个十秒的。
这个显卡不太冷 发表于 2020-9-30 00:07
这周没有实验课了。只有上次录这个十秒的。
实验课是什么
页:
[1]
2