AcWing 845. 八数码
原题链接
中等
日后复习用
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int bfs(string start)
{
string en="12345678x";
//定义目标状态
queue<string> q;//记录所有的变化的可能
unordered_map <string, int> d;//记录每种情况所产生的距离
//初始化队列和距离数组
q.push(start);
d[start]=0;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};//转移方式
while(q.size())
{
auto t=q.front();
q.pop();//取出队头元素并删除队头
int dis = d[t];//记录当前移动距离
if(t==en) return dis;
int k=t.find('x');//找到x,并转化为矩阵中的坐标
int x=k/3,y=k%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)
{
swap(t[k],t[a*3+b]);
//没有距离代表这是第一次遍历
if(!d.count(t))
{
d[t]=dis+1;//距离加一
q.push(t);//将该情况放入队内
}
//将状态还原
swap(t[k],t[a*3+b]);
}
}
}
//没有匹配的情况,返回-1
return -1;
}
void sove ()
{
string c,start;
for(int i=0;i<9;i++)
{
cin >> c;
start += c;
}
cout << bfs(start) << '\n';
}
int main()
{
cin.tie(0);
sove();
return 0;
}