gate

用时：60min?

\(IDA*\)

答案在\(15\)以内，考虑搜索
直接\(DFS\)的话会超时。

放学了

对于当前局面，用一个估价函数求出可能的步数。

#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\n");
            continue;
        }
        for(int md = 1;md <= 15;md++){
            dfs(sx,sy,0,md);
            if(flag){
                printf("%d\n",md);
                break;
            }
        }
        if(!flag) printf("-1\n");              
    }
    return 0;
}

Luogu P2324 [SCOI2005]骑士精神

原文：https://www.cnblogs.com/mogeko/p/13280127.html