题目
在一个 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 先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下：
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行，将 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
题目思路
我们用字符串压缩,将二维状态压缩为字符串,将目标态转化成"12345678x",如何快速利用string模拟x的翻转呢?
我们可以利用string中的find( )函数,找到x的位置,计算出x在二维状态下的坐标,然后用正常bfs的思路 进行上下左右的 四个方向的翻转 swap(x,x')交换之前与之后x对应的位置,如何快速求某个压缩状态下实际的操作数呢?我们可以使用unordered_map<string,int>d,将初始d[state]=0,后续更新swap(head,move)后得到的临时串,若为0,更新为distance+1,保证最小,push后 记得要返回初始状态 再次swap(head,move)
#include<bits/stdc++.h>
using namespace std;
int xx[4]={0,0,-1,1},yy[4]={1,-1,0,0};
string ans="12345678x"; //将二维压缩成一个 9位的字符串
int bfs(string state)
{
queue<string>q; //bfs用一个string_queue来写
unordered_map<string,int>d; //哈希表函数 用字符串作为下标,表示是当该字符串距离初始点 有多少步
d[state]=0; //将起点 标记0
while(!q.empty())
{
string t=q.front();
q.pop();
if(t==ans) //如果等于最终的数,就返回当前d[t]
{
return d[t];
}
int distance=d[t]; //为什么用一个临时变量 distance, //因为下面改变字符串后，字符串t更新，找不到该状态下的上一个状态*/
int k=t.find('x'); //找到'x'的位置
int x=k/3,y=k%3; //对应到二维x,y
for(int i=0;i<4;i++)
{
int a=x+xx[i],b=y+yy[i];
if(a>=0&&a<3&&b>=0&&b<3)
{
swap(t[a*3+b],t[k]); //x上下左右交换
if(!d.count(t)) //如果 d[t] ,字符串t没有访问过
{
d[t]=distance+1;
q.push(t);
}
swap(t[a*3+b],t[k]); //记得返回状态,不影响下次
}
}
}
return -1;
}
int main(){
string state;
for(int i=0;i<9;i++)
{
char ch;
cin>>ch;
state+=ch;
}
cout<<bfs(state);
}