|
|
本帖最后由 这个显卡不太冷 于 2020-9-24 20:42 编辑
[md]好的。
原因是上实验课太无聊了，教室的电脑是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[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
char op[5] = "udlr";
priority_queue<PIS, vector<PIS>, greater<PIS> > q;
q.push({f(st), st});
dist[st] = 0;
while(q.size())
{
auto t = q.top(); q.pop();
string state = t.second;
// out(state);
if(state == ed) break;
int step = dist[state];
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[0], dy = y + dir[1];
if(dx < 0 || dy < 0 || dx >= n || dy >= n) continue;
// src = state;
swap(src[x * n + y], src[dx * n + dy]);
if(!dist.count(src) || dist[src] > step + 1)
{
dist[src] = step + 1;
pair<string, int> o = {state, op};
q.push({step + 1 + f(src), src});
pre[src] = o;
}
swap(src[x * n + y], src[dx * n + dy]);
}
}
string res = "";
while(ed != st)
{
auto o = pre[ed];
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找了个试试。
[3.exe](data/attachment/forum/?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "3.exe")
也给一个编译好的文件吧。
[/md] |
|
发表于 2020-9-24 19:00:34
发表于 2020-9-28 18:31:39
发表于 2020-9-29 10:54:14
