题目链接：点我直达
一张成功ac的图片，哈哈！

这只是一种做法，网上好像还有其他做法
我的做法的注意事项：
1.走过的位置还可以再走的
2.需要一个结构体里面放置矩阵
3.需要一个map<int, bool>，将数码矩阵压缩成int数值
(0–>),如果int数值出现过就不要在入队
4.其他注意事项看我代码注释
使用map<int, bool>前提：
由于是使用广度优先算法，所以如果后面数码矩阵转换为的int数值在之前出现过，可以直接结束，因为步骤肯定不是最少的！
为什么需要一个map<int, bool>：
由于走过的位置还能再走，说明如果没有其他约束的话，会内存超限！（一开始没有考虑map，导致内存超限了，然后在自己电脑运行一个例子，一直运行导致我16G的内存占满，结果还没出现，电脑蓝屏。就是下面这个例子，答案是）

1 2 3 8 0 4 7 6 5 1 2 3 4 0 8 7 6 5 

讯享网#include <stdio.h> #include <queue> #include <map>  using namespace std; struct Node { 
    //step存放步数 int x, y, step; //存放上一次的移动方向 int lastX, lastY; //数码矩阵  int matrix[3][3]; } startNode, tempNode; /* 使用map实现判断数码矩阵是否入队 做法：将数码矩阵压缩成int数值(0-->),如果int数值出现过就不要在入队 */ map <int, bool> intMapBool; //目标数码矩阵  int targetMatrix[3][3]; int X[] = { 
   0, 0, 1, -1}; int Y[] = { 
   1, -1, 0, 0}; //转换为int数值通过数码矩阵  int toIntByMatrxi(int matrix[][3]) { 
    int result = 0; for(int i = 0; i < 3; i++) { 
    for(int j = 0; j < 3; j++) { 
    result = result * 10 + matrix[i][j]; } } return result; } void input(int matrix[][3]) { 
    for(int i = 0; i < 3; i++) { 
    for(int j = 0; j < 3; j++) { 
    scanf("%d", &matrix[i][j]); } } } //判断矩阵是否和目标矩阵相等  bool isEquality(int matrix[][3]) { 
    for(int i = 0; i < 3; i++) { 
    for(int j = 0; j < 3; j++) { 
    if(matrix[i][j] != targetMatrix[i][j]) { 
    return false; } } } return true; } bool check(Node node) { 
    if(node.x < 0 || node.x >= 3 || node.y < 0 || node.y >= 3) return false; //前一个动作和接下来的动作在y轴相反（增加了intMapBool后, 有点多余）  if(node.x == node.lastX && node.y == -node.lastY) return false; //前一个动作和接下来的动作在x轴相反（增加了intMapBool后, 有点多余）  if(node.x == -node.lastX && node.y == node.lastY) return false; return true; } int BFS() { 
    queue<Node> q; bool flag; startNode.step = 1; intMapBool[toIntByMatrxi(startNode.matrix)] = true; q.push(startNode); while(!q.empty()) { 
    Node top = q.front(); flag = isEquality(top.matrix); if(flag) { 
    return top.step; } q.pop(); for(int i = 0; i < 4; i++) { 
    tempNode.x = top.x + X[i]; tempNode.y = top.y + Y[i]; tempNode.step = top.step + 1; tempNode.lastX = top.x; tempNode.lastY = top.y; //普通检查  if(check(tempNode)) { 
    for(int i = 0; i < 3; i++) { 
    for(int j = 0; j < 3; j++) { 
    tempNode.matrix[i][j] = top.matrix[i][j]; } } //交换位置 int temp = tempNode.matrix[top.x][top.y]; tempNode.matrix[top.x][top.y] = tempNode.matrix[tempNode.x][tempNode.y]; tempNode.matrix[tempNode.x][tempNode.y] = temp; int Value = toIntByMatrxi(tempNode.matrix); //map检查  if(intMapBool[Value] == false) { 
    q.push(tempNode); intMapBool[Value] = true; } } } } } int main() { 
    input(startNode.matrix); input(targetMatrix); //找0的位置，因为0是作为起始点，这题目需要与0交换位置来移动矩阵  for(int i = 0; i < 3; i++) { 
    for(int j = 0; j < 3; j++) { 
    if(startNode.matrix[i][j] == 0) { 
    startNode.x = i; startNode.y = j; } } } printf("%d", BFS()); return 0; }