八数码
原题链接
题目描述：
在一个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
题目分析：
这道题是一道bfs的题目,但和我们平时做的bfs题不太一样，这道题不光要求某一个到达指定位置，而是要求所有的数都有一个确定的位置。
因此，用bfs求解时每一次交换都需要用字符串来存储整个交换后的数阵，然后判断这个数阵是否符合要求。
代码如下：
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
int bfs(string start)
{
queue q; //用队列来存储每次交换形成的字符串
unordered_map d;//将该字符串映射到它的交换次数
q.push(start); //将start放入队列
d[start]=0;
int fx[4]={1,0,-1,0};
int fy[4]={0,1,0,-1};
string end="12345678x"; //定义正确排列
while(q.size()) //bfs查找最小交换次数
{
string t=q.front(); //去除队头元素
q.pop();
int distance=d[t];
if(t==end) return distance; //如果队头元素为正确排列，结束查找
int k=t.find('x'); //找到字符串中x的位置，并将其转换为二维坐标
int xx=k/3;
int yy=k%3;
for(int i=0;i=0&&x=0&&y<3)//判断移动是否合法
{
int s=x*3+y;
swap(t[k],t[s]);//如果合法，进行移动
if(!d.count(t)) //看移动后的字符串是否与之前的重复
{
q.push(t); //如果不重复，则放入队列
d[t]=distance+1;
}
swap(t[k],t[s]); //还原原字符串
}
}
}
return -1; //如果没找到，则返回-1
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
string start;
for(int i=0;i>c;
start+=c;
}
cout<<bfs(start)<<endl;
return 0;
}
作者：li_wen_zhuo
