Luogu P2324 [SCOI2005]骑士精神（迭代加深搜索模板）

gate

用时：60min?

迭代加深搜索((IDDFS))：有深度上限的(DFS)。
当搜索深度(>MaxDeep)时就返回。若这次没有找到，则(MaxDeep+1)。
时间上，会比(BFS)慢一点，因为每次会重复搜索前面一层；
空间上，等于(DFS)的空间，远小于(BFS)。

剪枝优化((IDA*))：

乐观估计函数((evaluate))：求当前局面最少需要多少步。
若(now+eva>MaxDeep)，则可以返回。

对于本题，
答案在(15)以内，考虑搜索；枚举空格八方向移动。
设当前有(n)个位置错误的点，则至少移动(n-1)次（每次都将棋子移到正确的位置）才能归位。

(code)

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MogeKo qwq
using namespace std;

const int dx[8] = {2,2,-2,-2,1,1,-1,-1};
const int dy[8] = {1,-1,1,-1,2,-2,2,-2};

const int f[6][6] = {
    0,0,0,0,0,0,
    0,1,1,1,1,1,
    0,0,1,1,1,1,
    0,0,0,2,1,1,
    0,0,0,0,0,1,
    0,0,0,0,0,0
};

int t,a[6][6],sx,sy;
bool flag;
    
int read(){
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '*') return 2;
        ch = getchar();
    }
    return ch - '0';
}
    
bool check(int x,int y){
    return x>=1 && x<=5 && y>=1 && y<=5;
}

int eva(){
    int cnt = 0;
    for(int i = 1;i <= 5;i++)
        for(int j = 1;j <= 5;j++)
            if(a[i][j] != f[i][j])
                cnt++;
    return cnt;
}

void dfs(int x,int y,int dep,int maxdep){
    if(dep == maxdep){
        if(!eva()) flag = true;
        return;
    }
    for(int i = 0;i < 8;i++){
        if(flag) return;
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(!check(xx,yy)) continue;
        swap(a[x][y],a[xx][yy]);
        if(eva() + dep <= maxdep) dfs(xx,yy,dep+1,maxdep);
        swap(a[x][y],a[xx][yy]);
    }
}

int main(){
    scanf("%d",&t);
    while(t--){
        flag = false;
        for(int i = 1;i <= 5;i++)
            for(int j = 1;j <= 5;j++){
                a[i][j] = read();
                if(a[i][j] == 2)
                    sx = i, sy = j;
            }
        if(!eva){
            printf("0
");
            continue;
        }
        for(int md = 1;md <= 15;md++){
            dfs(sx,sy,0,md);
            if(flag){
                printf("%d
",md);
                break;
            }
        }
        if(!flag) printf("-1
");              
    }
    return 0;
}