题目描述
blablabla
样例
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <unordered_map>
using namespace std;
int bfs(string start)
{
//存结束状态
string end = "12345678x";
//定义队列
queue<string> q;
//用hash表存对应的距离和字符串
unordered_map<string, int> d;
//取队列的第一个,并且标记状态距离0
q.push(start);
d[start] = 0;
//方向盘移动
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
while(q.size())//当队列存在时
{
//取出队列头,删去
auto t = q.front();
q.pop();
//判断是否已经找到
int distance = d[t];
if(t == end) return distance;
//转换坐标
int k = t.find('x');
int x = k / 3, y = k % 3;
//方向盘选取状态
for(int i =0 ; i < 4; i++)
{
int a = x + dx[i];
int b = y + dy[i];
//未出界
if(a >= 0 && a < 3 && b >= 0 && b < 3)
{
//交换位置,并且之后还原,因为要循环四次
swap(t[k], t[a * 3 + b]);
//在哈希表找不到,距离+ 1,因为每次都是四个方向找,所以直接加1
if(!d.count(t))
{
d[t] = distance + 1;
q.push(t);
}
swap(t[k], t[a * 3 + b]);
}
}
}
return -1;
}
int main()
{
string c,start;
//初始化状态
for(int i = 0; i < 9; i++)
{
cin >> c;
start += c;
}
cout << bfs(start) << endl;
return 0;
}