题目描述
输入输出格式
输入格式：
第一行有一个正整数T(T<=10)，表示一共有N组数据。接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑士，*表示空位。两组数据之间没有空行。
输出格式：
对于每组数据都输出一行。如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出－1。
输入输出样例
说明
【题解】启发式搜索
#include<cstdio>
#include<algorithm>
using namespace std;
int dx[]= {-2,-1,1,2, 2, 1,-1,-2},
dy[]= { 1, 2,2,1,-1,-2,-2,-1};
int e[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 Get(int st[6][6]) {
int res=0;
for(int i=1; i<=5; i++)
for(int j=1; j<=5; j++)res+=(st[i][j]!=e[i][j]);
if(res)return res-1;
return res;
}
int ans;
int st[6][6];
inline int min(int a,int b) {
return a<b?a:b;
}
bool flag;
void dfs(int step,int x,int y) {
int temp=Get(st);
if(step+temp>15||flag&&step+temp>=ans)return ;
if(temp==0) {
ans=min(ans,step);
flag=true;
return ;
}
for(int i=0; i<8; i++) {
int r=x+dx[i],c=y+dy[i];
if(r<1||c<1||r>5||c>5)continue;
swap(st[r][c],st[x][y]);
dfs(step+1,r,c);
swap(st[r][c],st[x][y]);
}
}
char input[7];
int main() {
int T;
scanf("%d",&T);
while(T--) {
ans=0x3f3f3f3f;
flag=false;
int sx,sy;
for(int i=1; i<=5; i++) {
scanf("%s",input+1);
for(int j=1; j<=5; j++)if(input[j]=='*')sx=i,sy=j,st[i][j]=2;
else st[i][j]=input[j]-'0';
}
dfs(0,sx,sy);
if(ans!=0x3f3f3f3f)printf("%d
",ans);
else puts("-1");
}
return 0;
}