汇总了评论区和讨论里常见的问,每一步都有详细注释,希望对大家有帮助0.0
(参考了海绵宝宝大佬的题解并复制了几句他的原话,便于大家理解)
#include<bits/stdc++.h>
#include<unordered_map> //万能头里没有,自己加上
using namespace std;
//算法思路思路:将3*3矩阵转化为字符串,通过对字符串的操作来实现对九宫格状态转移的模拟。
//问题汇总:
//1.用一个队列保存当前获得的序列;
//2.用一个无序键值对保存各个序列与对应的交换次数;
//3.从队列中取出队头这个序列,计算出这个序列通过交换能得到的序列。如果能到得的序列是个新序列(哈希表中没有这个序列),
//就把这个新序列放入队尾,哈希表中记录新序列对应的交换次数;
//4.如果在上述过程中得到了结果序列,则输出交换次数,结束;
//5.如果最终没有得到结果序列。输出 -1;
//6.为什么这里要swap(t[a * 3 + b], t[k]);两次呢?因为这个for循环是遍历t的上下左右四
//个点,因为swap一下意味着xy和ab两个点换了位置,t现在是ab。判断完ab之后还要从xy出发去遍
//历其他三个点,所以要还原一下。
//7.为什么要用d.count(t)是不是0来判断这个点是否为有效点呢?因为我们要找到最短距离,要是不
//为零的话意味着用之前的换法已经换到这个状态过了,用现在这个状态接着换还如接着以前的状态换,
//以前的步数还少一些,而且这样才能把所有可能换到的状态全部枚举一遍。
queue<string> q; //保存状态,即八数码当前的字符串序列
unordered_map<string, int> d; //当前状态的字符串(序列)对应的移动次数(距离)
int bfs(string state)
{
q.push(state); //初始状态入队
d[state] = 0; //初始移动距离为0
string end = "12345678x"; //终止状态
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 }; //偏移量,用于向四个方向移动
while (!q.empty())
{
auto t = q.front();
q.pop();
int distance = d[t];
if (t == end) return distance; //如果已经到了最终状态返回总的交换次数
//将一维字符串下标转换为二维矩阵下标
int k = t.find('x'); //查询x在字符串中的下标
int x = k / 3, y = k % 3; //将下标转化为在3*3矩阵中的位置
for (int i = 0; i < 4; i++) //遍历所有可能转移的情况
{
int a = x + dx[i], b = y + dy[i]; //求可以与'x'进行交换操作的点(a,b)的坐标
if (a >= 0 && a < 3 && b >= 0 && b < 3) //没出界
{
//转移'x',即交换'x'与(可交换点a,b)的坐标——注意:交换的是两元素在字符串中的位置
//注意此处的k与a*3+b均为一维字符串中的下标(将(x,y)与(a,b)的下标由二维又转回一维)
swap(t[k], t[a * 3 + b]);
//如果当前状态是第一次遍历,记录距离,入队
if (!d.count(t))
{
d[t] = distance + 1;
q.push(t);
}
//还原状态,为下一种交换情况做准备
swap(t[k], t[a * 3 + b]);
}
}
}
//无法转换到目标状态,返回-1
return -1;
}
int main()
{
string s; //每次要输入的字符(直接定义成字符串,方便后面拼接)
string state; //起始状态
for (int i = 0; i < 9; i++)
{
cin >> s;
state += s;
}
cout << bfs(state) << endl;
return 0;
}