Description
在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士， 且有一个空位。在任何时候一个骑士都能按照骑 士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。 给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘： 为了体现出骑士精神，他们必须以最少的步数完成任务。
Input
第一行有一个正整数T(T<=10)，表示一共有N组数据。接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑士，*表示空位。两组数据之间没有空行。
Output
对于每组数据都输出一行。如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出－1。
Sample Input
2 10110 01*11 10111 01001 00000 01011 110*1 01110 01010 00100
Sample Output
7 -1
Solution： 首先，这是一道搜索题，限定了步数，因此可以采用BFS。 判重则采用的是string+set。 然而单纯这样，并不能通过所有的数据。 因此加入估价函数：
g[s]=当前图与目标图的不同的方块个数 用A*算法就可以通过这道题了。 #include<stdio.h> #include<iostream> #include<string> #include<queue> #include<algorithm> #include<set> using namespace std; struct Node{ string x; int step,g; bool operator <(const Node &a)const{ return step+g>a.step+a.g; } }; set<string>P; string ed="111110111100*110000100000"; int dx[]={1,2,2,1,-1,-2,-2,-1}; int dy[]={2,1,-1,-2,-2,-1,1,2}; priority_queue<Node>Q; bool judge(int x,int y){ return x>=0&&x<5&&y>=0&&y<5; } int g(string tmp){ int cnt=0; for(int i=0;i<25;i++) if(tmp[i]!=ed[i])cnt++; return cnt; } int BFS(string st){ while(!Q.empty())Q.pop(); P.clear(); int G=g(st); Q.push((Node){st,0,G}); while(!Q.empty()){ Node top=Q.top();Q.pop(); int pos; for(pos=0;pos<25;pos++) if(top.x[pos]=='*')break; int nx=pos/5,ny=pos%5; for(int i=0;i<8;i++){ int nxtx=nx+dx[i],nxty=ny+dy[i],nxtp=nxtx*5+nxty; string tmp=top.x; if(!judge(nxtx,nxty))continue; swap(tmp[nxtp],tmp[pos]); if(P.count(tmp))continue; P.insert(tmp); if(tmp==ed)return top.step+1; if(top.step<15&&top.step+g(tmp)<=15)Q.push((Node){tmp,top.step+1,g(tmp)}); } } return -1; } int main(){ char str[50]; int T; scanf("%d",&T); while(T--){ string st=""; for(int i=1;i<=5;i++){ scanf("%s",str); for(int j=0;j<5;j++) st+=str[j]; } if(st==ed)puts("0"); else printf("%d\n",BFS(st)); } }最后吐槽一下这诡异的评测机
