AcWing 3385. 玛雅人的密码-bfs 类似题(八数码)
原题链接
中等
作者:
debby
,
2023-03-12 15:35:32
,
所有人可见
,
阅读 139
C++ 代码
#include<iostream>
#include<cstring>
#include<queue>
#include<unordered_map>
using namespace std;
int n;
unordered_map<string, int> d;//从起点到现在的状态操作的次数
int bfs(string str)
{
queue<string> q;
q.push(str);
d[str] = 0;
while(q.size())
{
string s = q.front();
if(s.find("2012") != -1) return d[s]; //查询“2012”是否是子串,返回匹配的位置,如果不匹配会返回一个巨大的数(啊?相当于-1)
q.pop();
string t = s;
for(int i = 0; i < n - 1; i++)
{
swap(t[i], t[i + 1]);
//没有遍历过
if(!d.count(t))
{
q.push(t);
d[t] = d[s] + 1;//更新距离
}
t = s;//还原
}
}
return -1;
}
int main()
{
string start;
cin >> n >> start;
cout << bfs(start);
}