P2324 [SCOI2005] 骑士精神
大意
最小的步数达到要求的地方。
思路
这个题目的目标状态也很简约，就是形如题目中的样子，这个我们转换思路就是拿着这个空格去和旁边的格子不断的交换，但是这样产生的状态是很多的，为了剪枝，我们采用 IDA*，这个题目的估价函数有个很显然的写法，就是记录错误位置的个数，因此，一定小于等于...吗？我们考虑这样的情况，如果现在只需要一步，将空格和一个棋子交换，这样的实际步数是 \(1\)，但是你的估价函数给的是 \(2\)，显然不行，特判一下即可。然后我们就正常的去迭代加深的搜索就好。
代码
#include<iostream>
using namespace std;int T, ans = 1e9;
int a[6][6];
int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};int f(int b[6][6]){int res = 0;for(int j = 1;j <= 5;j ++){if(b[1][j] != 1) res ++;}for(int j = 1;j <= 5;j ++){if(b[5][j] != 0) res ++;}if(b[2][1] != 0) res ++;for(int j = 2;j <= 5;j ++){if(b[2][j] != 1) res ++;}if(b[4][5] != 1) res ++;for(int j = 1;j <= 4;j ++){if(b[4][j] != 0) res ++;}for(int j = 1;j <= 2;j ++){if(b[3][j] != 0) res ++;}if(b[3][3] != 2) res ++;for(int j = 4;j <= 5;j ++){if(b[3][j] != 1) res ++;}if(res == 2) return 1;return res;
}void dfs(int dp, int now, int cnt[6][6]){if(now >= ans) return;if(f(cnt) == 0){ans = now;return;}if(now + f(cnt) > dp) return;if(now > dp){return;}int sx = 0, sy = 0;for(int i = 1;i <= 5;i ++){if(sx) break;for(int j = 1;j <= 5;j ++){if(cnt[i][j] == 2){sx = i, sy = j;break;}}}for(int i = 0;i < 8;i ++){int nx = sx + dx[i];int ny = sy + dy[i];if(nx < 1 || ny < 1 || nx > 5 || ny > 5) continue;int sum[6][6];for(int p = 1;p <= 5;p ++){for(int q = 1;q <= 5;q ++){sum[p][q] = cnt[p][q];}}swap(sum[sx][sy], sum[nx][ny]);dfs(dp, now + 1, sum);}
}int main(){cin >> T;while(T --){for(int i = 1;i <= 5;i ++){string s; cin >> s;for(int j = 0;j < 5;j ++){if(s[j] == '*') a[i][j + 1] = 2;else a[i][j + 1] = s[j] - '0';}}ans = 1e9;for(int dp = 1;dp <= 15;dp ++){dfs(dp, 0, a);if(ans <= 15) break;}if(ans <= 15){cout << ans << '\n';}else{cout << -1 << '\n';}}return 0;
}