题目描述

输入输出格式

输入格式：

 

第一行有一个正整数T(T<=10)，表示一共有N组数据。接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑士，*表示空位。两组数据之间没有空行。

 

输出格式：

 

对于每组数据都输出一行。如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出－1。

 

输入输出样例

输入样例#1：

21011001*1110111010010000001011110*1011100101000100

输出样例#1：

7-1

说明

 

思路：A*

 错因：字母x,y的大小写混淆。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int fxy[6][6]={
   {
   9,9,9,9,9,9},               {
    9,1,1,1,1,1},               {
    9,0,1,1,1,1},               {
    9,0,0,9,1,1},               {
    9,0,0,0,0,1},               {
    9,0,0,0,0,0}};int dx[8]={
   1,1,-1,-1,2,-2,2,-2};int dy[8]={
   2,-2,2,-2,1,-1,-1,1};int T,X,Y,ans,map[6][6];char c;int H(){    int bns=0;    for(int i=1;i<=5;i++)        for(int j=1;j<=5;j++)            if(map[i][j]!=fxy[i][j])    bns++;    if(map[3][3]!=9)    bns-=1;    return bns;}void dfs(int k,int X,int Y,int g){    int h=H();    if(!h){        ans=g;        return ;    }    if(h+g>k||ans>=0||g==k)    return ;    for(int i=0;i<8;i++){        int x=dx[i]+X;        int y=dy[i]+Y;        if(x>=1&&y>=1&&x<=5&&y<=5){            swap(map[X][Y],map[x][y]);            dfs(k,x,y,g+1);            swap(map[X][Y],map[x][y]);        }    }}int main(){    scanf("%d",&T);    while(T--){        ans=-1;        for(int i=1;i<=5;i++){            for(int j=1;j<=5;j++){                cin>>c;                if(c=='1')    map[i][j]=1;                else if(c=='0')    map[i][j]=0;                else{                    X=i,Y=j;                    map[i][j]=9;                }            }        }                for(int k=0;k<=15;k++){            dfs(k,X,Y,0);            if(ans>=0){                printf("%d\n",ans);                break;            }        }        if(ans==-1)    cout<<"-1"<