AcWing 845. 八数码
原题链接
中等
作者:
YMYS
,
2024-03-30 23:35:33
,
所有人可见
,
阅读 22
//2024.3.30
//https://www.acwing.com/problem/content/847/
//八数码
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
using namespace __gnu_cxx;
int dx[4]={0,0,1,-1}, dy[4]={1,-1,0,0};
queue<string> q_str;
unordered_map<string, int> hash_map;//哈希表。int存的是移动次数
int bfs(string start)
{
string end = "12345678x";//定义最终目的字符串
//初始化
hash_map[start] = 0;//标记start的距离为0
q_str.push(start);
while (q_str.size())
{
auto t = q_str.front();
q_str.pop();
//res 表示目前这个 t 所对应的移动次数
int res = hash_map[t];
if(t == end) return res;
int k = t.find("x");
for(int i=0;i<4;i++){
int x = k/3 + dx[i], y = k%3 + dy[i];
if(x>=0 && x<3 && y>=0 && y<3){//判断新的(x,y)是否在合法的范围内
swap(t[k], t[3*x + y]);
if(!hash_map.count(t)){//判断swap后的t是否是第一次遇到,这样是为了防止在queue中加入重复的stirng
q_str.push(t);
hash_map[t] = res+1;
}
swap(t[k], t[3*x + y]);//因为要执行四次的for循环,所以我们需要恢复到最初的t的状态
}
}
}
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);
string c;
string start;
for(int i=0;i<9;i++){
cin>>c;
start+=c;
}
cout << bfs(start) <<endl;
return 0;
}