AcWing 845. 八数码
原题链接
中等
作者:
YMYS
,
2024-03-30 21:47:24
,
所有人可见
,
阅读 18
//2024.3.30
//https://www.acwing.com/problem/content/847/
//八数码
/*
思路:常见的bfs模式套路,在queue队列中不断加入状态,直到把所有的状态都遍历完。
*** 这里的思路是把二维的char数组,转化为一维的string,判断其是否等于终点string(因为终点stirng是固定的"12345678x")
//
//注意!!!什么时候适用于使用Bfs?当题目中提出一圈一圈的遍历点的时候就用bfs,模板套路一样
//
*/
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>//哈希表
using namespace std;
int bfs(string start)
{
//定义目标状态
string end = "12345678x";
//定义队列和dist数组
queue<string> q;
unordered_map<string, int> d;
//初始化队列和d(dist)数组
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 distance = d[t];
if(t == end) return distance;
//查询x在字符串t中的下标,然后转换为在矩阵中的坐标
int k = t.find('x');
int x = k / 3, y = k % 3;
//上下左右遍历一下(不管是不是对的数,都会进行遍历,去加入queue)
for(int i = 0; i < 4; i++)
{
//求转移后x的坐标
int a = x + dx[i], b = y + dy[i];
//当前坐标没有越界
if(a >= 0 && a < 3 && b >= 0 && b < 3)
{
//转移x
swap(t[k], t[a * 3 + b]);
//如果当前状态是第一次遍历,记录距离,入队
if(!d.count(t))//保证队中没有重复元素
{
d.insert({t, distance+1});
//也可以这样【d[t] = distance + 1】
q.push(t);
}
//还原状态,为下一种转换情况做准备【这行代码只是作用于上下左右四种情况,对while的每一层循环无用】
swap(t[k], t[a * 3 + b]);
}
}
}
//无法转换到目标状态,返回-1(找到的话,会从上面的return出去)
return -1;
}
int main()
{
#ifdef ABC
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
char c;
string start;
//为什么这里要用c坐中间件?
//答:因为给的数据之间有空格,不然的话string start这个字符串之间会有空格存在
for(int i = 0; i < 9; i++)
{
cin >> c;
start += c;
}
cout << bfs(start) << endl;
return 0;
}