算法-bfs-八数码
题目一
解题思路
将每一串字符都想象成一个点,已知起点和终点,每一次更新相邻的节点,采用bfs得到到达终点的最短路径。
数据结构:
unordered_map(哈希表)来存储每种字符串对应情况需要移动的次数。
queue(队列)存储当前遍历及下一步遍历的情况
边界问题:
设x在字符串中的下标为k,则x在3*3矩阵中的坐标为(k/3,k%3);
isValid函数判断每次x移动变换是否合理(x,y>=0&&x,y<3);
dfs函数返回值为-1,代表该情况无解(无论怎么变化都无法成为最终的效果)。
代码模板
#include<iostream>
#include<unordered_map>
#include<queue>
using namespace std;
string endst="12345678x";//目标字符串
queue <string> q;//辅助队列,存储下一步变换可能的情况
unordered_map<string,int>d;//某一情况的最短交换次数(最短距离)
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};//上下左右变换坐标
bool isVaild(int x,int y)//判断变换是否合理
{
return x>=0&&x<3&&y>=0&&y<3;
}
int bfs(string state)
{
q.push(state);
d[state]=0;
while(q.size())
{
auto t=q.front();//返回队列头部的元素
q.pop();//删除队头元素
int dis=d[t];
if(t==endst) return dis;
int k=t.find('x');
int x=k/3,y=k%3;//字符串变换为矩阵下标
for(int i=0;i<4;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(isVaild(nx,ny))
{
swap(t[nx*3+ny],t[k]);//交换后字符串已改变,在push中添加到队列尾部
if(!d.count(t))//检查哈希表中是否已经存在该情况,不存在则更新
{
d[t]=dis+1;
q.push(t);
}
swap(t[nx*3+ny],t[k]);//恢复原本情况
}
}
}
return -1;
}
int main()
{
string state;
for(int i=0;i<9;i++)//读入初始字符串
{
char st;
cin>>st;
state+=st;
}
cout<<bfs(state)<<endl;
return 0;
}
原文地址:https://blog.csdn.net/xx_xb/article/details/140738583
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!