象棋（搜索+优化）

Lutece (uestc.edu.cn)

哦突然想起来这个搜索叫启发式搜索......

#include "bits/stdc++.h"
using namespace std;
char s[10][10];
int dx[8]={-2,-2,-1,-1,1,1,2,2};
int dy[8]={-1,1,-2,2,-2,2,-1,1};
int ans;
char ss[6][6]={"11111","01111","00*11","00001","00000"};
bool ck(){
    int i,j;
    for (i=0;i<5;i++)
        for (j=0;j<5;j++)
            if (s[i][j]!=ss[i][j]) return false;
    return true;
}
void dfs(int dp,int nx,int ny){
    int i,j,zt=0;
//    for (i=0;i<5;i++){
//            printf("%s\n",s[i]);
//            
//        }printf("\n\n");
    if (dp>15) return;
    if (ck()){
        ans=min(ans,dp);
        return;
    }
    for (i=0;i<5;i++)
        for (j=0;j<5;j++)
            if (s[i][j]!=ss[i][j]){
                zt++;
                if (dp+zt>ans) return;
            }
    for (i=0;i<8;i++){
        if(nx+dx[i]<0 || nx+dx[i]>4 || ny+dy[i]<0 || ny+dy[i]>4) continue;
        swap(s[nx][ny],s[nx+dx[i]][ny+dy[i]]);
        dfs(dp+1,nx+dx[i],ny+dy[i]);
        swap(s[nx][ny],s[nx+dx[i]][ny+dy[i]]);
    }
}
int main(){
    int i,j,t,nx,ny;
    scanf("%d",&t);
    while (t--){
        for (i=0;i<5;i++)
            scanf("\n%s",s[i]);
        for (i=0;i<5;i++)
            for (j=0;j<5;j++)
                if (s[i][j]=='*')
                    nx=i,ny=j;
        ans=16;
        dfs(0,nx,ny);
        printf("%d\n",(ans==16?-1:ans));
    }
    return 0;
}