如果想要更好的体验,可以到我的博客去看
我使用的算法是IDA_star
好处在于效率高,不用hash
我们想想,假设每一步都是有意义的,那么一个数字成功对上也要移动他们的曼哈顿距离次
所以,我们将估价函数设计为所有数字与目标状态中数字的曼哈顿距离之和(当然0不算,否则你就可以高兴的WA了)
还有一个显然的优化,就是记录上一次的操作
而且我们不一定要用二维数组,可以用一个string来保存状态。对于一个string中的下标i,纵坐标为i/3, 横坐标为i%3。对于二维数组下标x, y, string中的下标便为x * 3 + y
还有不明白的,请看代码
//Author:WFZWF
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
string st, ed;
int depth;
int hfunc(string st) {
int ans = 0;
for (register int i = 0; i < st.size(); ++i) {
if (st[i] == '0') continue;
int j = ed.find(st[i]), r = i / 3, c = i % 3;
int x = j / 3, y = j % 3;
ans += abs(r - x) + abs(c - y);
}
return ans;
}
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
bool dfs(int now, int pre) {
int cnt = hfunc(st);
if (!cnt) return 1;
if (now + cnt > depth) return 0;
int pos = st.find('0'), x = pos / 3, y = pos % 3;
for (register int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx > 2 || ny < 0 || ny > 2 || nx * 3 + ny == pre) continue;
swap(st[pos], st[nx * 3 + ny]);
if (dfs(now + 1, pos)) return 1;
swap(st[pos], st[nx * 3 + ny]);
}
return 0;
}
int main() {
for (register int i = 1; i <= 9; ++i) {
char s[2];
scanf("%s", s);
st += s[0] == 'x' ? '0' : s[0];
}
int cnt = 0;
for (register int i = 0; i < st.size(); ++i)
if (st[i] != '0')
for (register int j = 0; j < i; ++j)
if (st[j] != '0') cnt += st[i] > st[j];
if (cnt & 1) {
puts("-1");
return 0;
}
ed = "123456780";
for (depth = hfunc(st); !dfs(0, -1); ++depth);
cout << depth;
}
洛谷题解