T22:05:00+08:00
洛谷：P2324 SCOI2005骑士精神 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
由于要求得最小的步数，使用 dfs 的话就只有全部跑完才能确定得到的结果是最小的结果。
| C++ |
|---|
| const int dx[] = {0, 1, 1, -1, -1, 2, 2, -2, -2};
const int dy[] = {0, 2, -2, 2, -2, 1, -1, 1, -1};
int ans = 16;
void dfs(int x, int y, int depth = 0) {
if (depth > 15) return;
if (check()) {
ans = min(ans, depth-1);
return;
}
for (int i = 1; i <= 8; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx < 1 || xx > 5 || yy < 1 || yy > 5) continue;
swap(m[xx][yy], m[x][y]);
dfs(xx, yy, depth+1);
swap(m[xx][yy], m[x][y]);
}
}
|
而每一步决策有 8 个方向，这颗树的增长速度十分恐怖 \(8^n\)，而最大步数为 15，那么就需要 \(8^{15}\) 次才能得到结果，绝对超时。
考虑到答案可能在较低层中，而由于深搜的特点，到最深层才会返回，这样会多搜很多东西。
于是可以考虑限制搜索深度，迭代放宽深度。
| C++ |
|---|
| int ans = 16;
void dfs(int x, int y, int maxdepth, int depth = 0) {
if (depth > maxdepth) return;
// ...
}
int main () {
// ...
for (int i = 1; i <= 15; i++) {
dfs(x, y, i);
if (ans < 16) break;
}
// ...
}
|
然而这种“优化”也只能保证答案在较低层时不会超时，若答案在最深层，仍然要遍历所有状态才能得到结果。
考虑有这样一个函数：
\[
f(x) = g(x) + h(x)
\]
其中 \(g\) 为距离起点的距离函数，\(h\) 为距离终点的距离函数。
那么很显然，结合迭代加深，如果当前的 \(f\) 大于了 \(maxdepth\)，那么不能在限定步数内到达终点。
然而我们并不知道确切的 \(h\)，所以我们可以找出一个能够估计到终点的距离函数 \(h^*(x) \leq h(x)\)，保证小于等于是由于为防止估计错误而使 \(f\) 比实际大而导致判断不能到达。
针对本题来说，不难想到一个 \(h^*(x) = 不在原位置的棋子数（不包括空位）\)，可以想象一个最理想的过程，当前空位依次移动到每一个不在原位置的棋子处，每一次移动归位一个棋子。
完整代码：
| C++ |
|---|
| #include <iostream>
using namespace std;
char m[6][7];
const char goal[6][7] = {
{"000000"},
{"011111"},
{"001111"},
{"000*11"},
{"000001"},
{"000000"},
};
char read() {
char c;
while ((c = getchar()) != '0' && c != '1' && c != '*');
return c;
}
const int dx[] = {0, 1, 1, -1, -1, 2, 2, -2, -2};
const int dy[] = {0, 2, -2, 2, -2, 1, -1, 1, -1};
int eval() {
int cnt = 0;
for (int i = 1; i <= 5; i++) {
for (int j = 1; j <= 5; j++) {
if (m[i][j] != goal[i][j]) cnt++;
}
}
return cnt ? cnt-1 : 0;
}
int ans;
void dfs(int x, int y, int maxdepth, int depth = 0) {
int e = eval();
if (depth + e > maxdepth) return;
if (!e) {
ans = min(ans, depth);
return;
}
for (int i = 1; i <= 8; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx < 1 || xx > 5 || yy < 1 || yy > 5) continue;
swap(m[xx][yy], m[x][y]);
dfs(xx, yy, maxdepth, depth+1);
swap(m[xx][yy], m[x][y]);
}
}
int main() {
int T; cin >> T;
int x, y;
while (T--) {
ans = 16;
for (int i = 1; i <= 5; i++) {
for (int j = 1; j <= 5; j++) {
m[i][j] = read();
if (m[i][j] == '*') {
x = i;
y = j;
}
}
}
for (int i = 1; i <= 15; i++) {
dfs(x, y, i);
if (ans < 16) break;
}
cout << (ans < 16 ? ans : -1) << endl;
}
return 0;
}
|