哦突然想起来这个搜索叫启发式搜索......
#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;
}