题解 P1379 【八数码难题】

如果想要更好的体验，可以到[我的博客](https://www.luogu.org/blog/I-AK-IOI/)去看 我使用的算法是IDA_star 好处在于效率高，不用hash 我们想想，假设每一步都是有意义的，那么一个数字成功对上也要移动他们的曼哈顿距离次 所以，我们将估价函数设计为所有数字与目标状态中数字的曼哈顿距离之和（当然0不算，否则你就可以高兴的WA了） 还有一个显然的优化，就是记录上一次的操作 而且我们不一定要用二维数组，可以用一个string来保存状态。对于一个string中的下标i，纵坐标为i/3, 横坐标为i%3。对于二维数组下标x, y, string中的下标便为x * 3 + y 还有不明白的，请看代码 ```cpp #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #include<bits/stdc++.h> 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;//0不算，否则会WA int j = ed.find(st[i]), r = i / 3, c = i % 3; int x = j / 3, y = j % 3; //横坐标为/3, 纵坐标为%3 ans += abs(r - x) + abs(c - y); } return ans; } const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, -1, 1}; //IDA_star //除了估价函数，还有一个显然的优化是记录上一次的操作 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; //数组中的下标为横坐标*3+纵坐标 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() { cin >> st; ed = "123804765"; depth = hfunc(st); while (depth <= 27 && !dfs(0, -1)) ++depth; cout << depth << endl; } ``` 跑得还很快 [评测记录](https://www.luogu.org/record/22955029)