描述 在九宫格里放在1到8共8个数字还有一个是空格，与空格相邻的数字可以移动到空格的位置，问给定的状态最少需要几步能到达目标状态（用0表示空格）： 1 2 3 4 5 6 7 8 0
输入 输入一个给定的状态。
输出 输出到达目标状态的最小步数。不能到达时输出-1。
输入样例 1 2 3 4 0 6 7 5 8
输出样例 2
题解 首先看题是一道搜索题目，输入一个33的数组，找到目标状态，首先需要找到起点，也就是0点，然后按照上下左右四个方向移动0点，也就是和0点旁边的四个点交换位置，当然是在条件允许的情况下，如果0点在第一排，也就是mat[0][i]的情况下，则不可以向上方向走，其他四个边界方向如此，也就是不越界的情况下，然后再就是普通的bfs广度搜索了，判断当前节点按方向是否可以走下一个节点，如果可以则进入队列，当队列为空退出循环的时候也就说明没有答案。 难点在如何判断当前点的状态那个方向不可以走，因为是33的矩阵，所以使用int类型，把矩阵转换成数字，然后两层循环找到0的位置，并且判断0的边界情况。如果该方向可以走的话，更新矩阵。
#include <iostream> #include <map> #include <queue> using namespace std; queue<int> q; map<int, int> vis; map<int, int> step; int dir[4][2] = {-1,0,0,1,1,0,0,-1}; //方向数组 上 右 下 左 int state; //初始状态 int mat[3][3]; //使用数组存状态好计算 int c,r; //记下当前状态下0位置的 void input(){ int temp = 0; for (int i = 0; i < 3;i++) for (int j = 0; j < 3;j++){ cin >> mat[i][j]; temp = mat[i][j] + temp * 10; } state = temp; } int can_move(int u,int d){ //u为当前数字状态，d为方向 for(int i=2;i>=0;i--) for(int j=2;j>=0;j--){ mat[i][j] = u % 10; u/=10; if(mat[i][j] == 0){ r = i; c = j; } } //当向上走的时候，0在最上一列不可以走以此类推 if((d == 0 && r == 0) || (d == 1 && c == 2) || (d == 2 && r == 2) || (d == 3 && c == 1)) return 0; return 1; } int move_to(int u,int i){ int tmp = 0; int x = r + dir[i][0];// 0被移动到的位置 int y = c + dir[i][1]; mat[r][c] = mat[x][y]; mat[x][y] = 0; for(int i=0;i<3;i++) for(int j=0;j<3;j++) tmp = mat[i][j] + tmp * 10; return tmp; } int bfs(int state){ q.push(state); vis[state] = 1; step[state] = 0; while(q.size()){ int u, v; //ui作為队首的状态 u = q.front(); q.pop(); if(u == 123456780) return step[u]; for (int i = 0; i < 4;i++){ //四个方向移动 if(can_move(u,i)){ //如果可以走 v = move_to(u,i); if(!vis[v]){ vis[v] = 1; step[v] = step[u] + 1; q.push(v); } } } } return -1; } int main(){ input(); int ans = bfs(state); cout << ans << endl; return 0; }该代码转载自https://blog.csdn.net/qq_41636123/article/details/83010868 并非本作者原创
