c++代码+详细注释
#include<iostream>
#include<algorithm>
#include<queue>
#include<unordered_map>
using namespace std;
int bfs(string start)
{
string end="12345678x";//储存移动后想要的结果
queue<string> q;
unordered_map<string,int> d;
q.push(start); //初始化数据,从start开始bfs
d[start]=0; //初始化数据,start的距离映射为0;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};//可交换位置的四个方向,分别为右、下、左、上
while(!q.empty())//如果队列 q 不为空就一直循环,或者遇到想要的结果就返回
{
auto t=q.front();//t 储存队列 q 中的队头的字符串,接下俩每次都从队头的数据进行操作
q.pop();//储存完就可以删除队列 q 中该点的元素,因为接下来要对他进行操作
int distance=d[t];//用变量distance储存t字符串情况时到start情况的距离(需要走的步骤)
if(t==end) return distance;//如果t 正好满足 12345678x 就返回结果
int k=t.find('x');//k等于x在t字符串中 一维数组的坐标
int x=k/3,y=k%3; //计算得x,y为3*3的二维坐标
for(int i=0;i<4;i++)//开始准备移动操作
{
int a=x+dx[i],b=y+dy[i];//记录每次移动后的位置
if(a>=0&&a<3&&b>=0&&b<3)//如果a,b不越界,说明可以移动
{
swap(t[k],t[a*3+b]);// x与满足条件的(上下左右)元素交换位置
if(!d.count(t))//现在t是交换完后的情况,如果t在d 中没有出现过,进行以下操作
{
d[t]=distance+1;//记录移动后的距离
q.push(t);//因为在d中没有出现过,所以将现在的t放入q中,进行新的bfs操作
}
swap(t[k],t[a*3+b]);//返回原本的状态,x和别的方向并且满足条件的元素进行位置交换
}
}
}
return -1;//如果循环结束,说明无解,返回-1;
}
int main()
{
char s[2];
string state;
for(int i=0;i<9;i++)
{
cin>>s;
state += *s;
}
cout<<bfs(state)<<endl;
return 0;
}
有问题或没解释清楚的地方 希望大佬能够指正