题目描述
初始状态的步数就算1，哈哈
输入：第一个3*3的矩阵是原始状态，第二个3*3的矩阵是目标状态。
输出：移动所用最少的步数
Input
2 8 3
1 6 4
7 0 5
1 2 3
8 0 4
7 6 5
Output
6
注：
题目意思是，8个数加一个空位（0），每一步可以让周围的数（上下左右）走到这个空位里来，问初始矩阵最少要走几步才能变成结果矩阵。
1、二维数组作为函数变量传递，可以直接改变传入的数组本身，不需要引用，C++不支持对数组进行引用；
2、BFS第一个入队的是空位0的坐标，记第一个入队的Node的上一个坐标是空位0的坐标，不一定是（0，0）；
3、判断新走的一步的位置有效if(judgeP(newX,newY)&&(newX!=top.lastx||newY!=top.lasty))而不是if(judgeP(newX,newY)&&newX!=top.lastx&&newY!=top.lasty)
#include<stdio.h>
#include<queue>
using namespace std;
int Matrix[3][3];
int final[3][3];
int wx[4]={0,0,1,-1};
int wy[4]={-1,1,0,0};
struct node{int M[3][3];int lastx,lasty;int step;int x ,y;
}Node;int judgeP(int x,int y){if(x>=3||x<0)return 0;if(y>=3||y<0)return 0;return 1;
}
int judgeS(int NowM[][3]){for(int i=0;i<3;i++)for(int j=0;j<3;j++){if(NowM[i][j]!=final[i][j])return 0;}return true;
}
void copyM(int NewM[][3],int oldM[3][3]){for(int i=0;i<3;i++){for(int j=0;j<3;j++){NewM[i][j]=oldM[i][j];}}
}
void print(int M[3][3]);
int equlM(int M1[][3],int M2[][3])
{for(int i=0;i<3;i++){for(int j=0;j<3;j++){if(M1[i][j]!=M2[i][j])return 0;}} return 1;
}
int BFS(int x,int y)
{queue<node> Q;Node.x=x;Node.y=y;Node.step=1;Node.lastx=x;Node.lasty=y;copyM(Node.M,Matrix);Q.push(Node);node top;while(!Q.empty()){top=Q.front();Q.pop();for(int i=0;i<4;i++){int newX=top.x+wx[i];int newY=top.y+wy[i];if(judgeP(newX,newY)&&(newX!=top.lastx||newY!=top.lasty)){Node.x=newX;Node.y=newY;Node.step=top.step+1;Node.lastx=top.x;Node.lasty=top.y;copyM(Node.M,top.M);Node.M[top.x][top.y]=top.M[newX][newY];Node.M[newX][newY]=0;Q.push(Node);} }if(equlM(top.M,final)){// printf("\n-------BFS--------\n");// print(top.M);// printf("\n-------BFS--------\n");return top.step; } }}
void print(int M[3][3])
{for(int i=0;i<3;i++){for(int j=0;j<3;j++){printf("%d ",M[i][j]);}printf("\n");}
}
int main()
{int x,y;for(int i=0;i<3;i++){for(int j=0;j<3;j++){scanf("%d",&Matrix[i][j]);if(Matrix[i][j]==0){x=i;y=j;}}getchar();}for(int i=0;i<3;i++){for(int j=0;j<3;j++){scanf("%d",&final[i][j]);}if(i!=2)getchar();}// print(Matrix);
// print(final);printf("%d\n",BFS(x,y));}