「Bzoj 1085」「SCOI2005」骑士精神 (IDA*)

Bzoj 1085
这种限制步数的题目可以用迭代加深搜索做。并且这种只有一个空格的题目，一般就是用空格的坐标去遍历其他有东西的坐标，然后相当于东西的移动。
本题直接DFS超时严重，样例都过不了。
我们考虑加一个估价函数剪枝：当前步数$+$当前状态和目标状态棋盘上的差异数(具体看代码)$<$迭代加深的步数
之后就很快了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 5;
const int gl[MAXN + 2][MAXN + 2] = {
    {1, 1, 1, 1, 1}, 
    {0, 1, 1, 1, 1}, 
    {0, 0, 2, 1, 1},     
    {0, 0, 0, 0, 1}, 
    {0, 0, 0, 0, 0}
};
const int dx[8] = {1, 2, -1,  2, -2,  1, -1, -2};
const int dy[8] = {2, 1,  2, -1,  1, -2, -2, -1};
int a[MAXN + 2][MAXN + 2];
int kx, ky, flag;
char s[MAXN];
bool check() {
    if (a[2][2] != 2) return false;
    for (int i = 0; i < MAXN; i++)
    for (int j = 0; j < MAXN; j++) if (gl[i][j] != a[i][j]) return false;
    return true;
}
bool gv(int st, int k) {
    int tot = 0;
    for (int i = 0; i < MAXN; i++)
    for (int j = 0; j < MAXN; j++) if (gl[i][j] != a[i][j]) tot++;
    if (st + tot > k) return false;
    return true;
}
void dfs(int x, int y, int st, int k) {
    if (flag) return ;
    if (check()) {flag = true; return ;}
    if (st >= k) return ;
    for (int i = 0; i < 8; i++) {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx >= 0 && ty >= 0 && tx < MAXN && ty < MAXN) {
            swap(a[x][y], a[tx][ty]);
            if (gv(st, k)) dfs(tx, ty, st + 1, k);
            swap(a[x][y], a[tx][ty]);
        }
    }
}
void clean() {
    flag = kx = ky = 0, ms(a, 0);
}
void solve() {
    clean();
    for (int i = 0; i < MAXN; i++) {
        scanf("%s", s);
        for (int j = 0; j < MAXN; j++) {
            if (s[j] == '0') a[i][j] = 0; else if (s[j] == '1') a[i][j] = 1; else if (s[j] == '*') a[i][j] = 2, kx = i, ky = j;
        }
    }
    for (int i = 1; i <= 15; i++) {
        dfs(kx, ky, 0, i);
        if (flag) {
            printf("%d\n", i);
            return ;
        }
    }
    if (!flag) printf("-1\n");
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    int T; scanf("%d", &T); 
    while (T--) solve();
    return 0;
}