AcWing 845. 八数码(3阶数字华容道)：bfs求最短路，状态表示困难

文章目录

• • • 题目
    • 题目分析

题目

题目链接：AcWing 845. 八数码(数字华容道)

在一个3×3的网格中，1~8这8个数字和一个“x”恰好不重不漏地分布在这3×3的网格中。

例如：

1 2 3
x 4 6
7 5 8

在游戏过程中，可以把“x”与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 x

例如，示例中图形就可以通过让“x”先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1 2 3 \ 1 2 3 \ 1 2 3\ 1 2 3
x 4 6 \ 4 x 6 \4 5 6 \4 5 6
7 5 8 \ 7 5 8 \7 x 8 \7 8 x
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

输入格式
输入占一行，将3×3的初始网格描绘出来。

例如，如果初始网格如下所示：

1 2 3
x 4 6
7 5 8

则输入为：1 2 3 x 4 6 7 5 8

输出格式
输出占一行，包含一个整数，表示最少交换次数。

如果不存在解决方案，则输出”-1”。

输入样例：
2 3 4 1 5 x 7 6 8
输出样例
19

题目分析

任意的初始状态start，比如是start=“23415x769”,最终状态是end=“12345678x” 求初始状态变成 最终状态end的最少步数。

这里需要抽象一下，将一个状态(一个字符串) 抽象成图中的一个结点a，如果一个状态可以变成另一个状态b，就在图中两个结点a和b之间建立一条有向边$a\to b$，边的权值是1.

那么该问题就变成：给定一个起点 和一个终点，从起点到终点最少走多少步。 可以使用BFS()来求最短路。

BFS()需要两个数据结构：1个队列queue，一个距离数组dist[ ]

难点如下:

状态表示复杂：这里每个状态是一个3 ×3的小矩阵

如何记录每个状态到初始状态的距离

解决方法：

用一个字符串表示一个3 ×3的小矩阵，比如是start=“23415x769”,最终状态是end=“12345678x” ，那么队列就可以是queue<string>

距离用哈希表来存，unordered_map<string ,int>

想明白这些表示的问题，真正的难点在于如何实现状态转移

start="23415x769"这个状态可以状态成几种状态？
1） 需要把这个一维字符串转换成二维的小矩阵
映射方法(假设矩阵每行m个数) 则 一维下标t转换为二维下标(x,y) 有如下公式：

x= t /m; //m是矩阵每行元素个数，本例中 m = 3 y=t% m;

2）状态转移：二维矩阵中的点(x,y)可以转移到它的上下左右四个方向。

3）最后再将二维矩阵坐标映射成1维字符串中的下标。
二维小矩阵中坐标恢复到一维坐标：

t= x * m+ y; //m是矩阵每行元素个数，本例中 m = 3

然后就是标准的bfs模板。
请看代码：

ac代码

#include<iostream> #include<algorithm> #include<unordered_map> #include<queue>#include<string> using namespace std;int bfs(string start){string end="12345678x";//终点queue<string> q; unordered_map<string,int> d;//距离数组q.push(start);d[start]=0;int dx[4]={0,0,-1,1}, dy[4]={1,-1,0,0};while(q.size()){auto t=q.front();//t为字符串q.pop();int dist=d[t];if(t==end) return dist; //到了终点 返回 dist//状态转移int k=t.find('x'); //找到x的位置//一维数组下标转化为二维数组下标（x，y）int x= k/3,y=k %3; //(x,y)为空格x的位置for(int i=0;i<4;i++){int a= x + dx[i] , b =y +dy[i]; //（a，b）为空格上下左右的某一个值if(a>= 0 && a<3 && b>=0 && b<3 ){swap(t[k],t[a*3+b]); //二维下标对应到一维下标 ,状态更新if(!d.count(t)){ //之前没搜到d[t]=dist+1;q.push(t);}swap(t[k],t[a*3+b]); //状态恢复}}}return -1; //到不了终点 返回-1 }int main(){string start;for(int i=0;i<9;i++){char c;cin>>c;start+= c;}cout<<bfs(start) <<endl;return 0;}

总结

以上是生活随笔为你收集整理的AcWing 845. 八数码(3阶数字华容道)：bfs求最短路，状态表示困难的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。