蓝桥打卡-5-青蛙跳杯子(八数码)
作者:
因为yxc爱上编程
,
2024-04-07 10:45:02
,
所有人可见
,
阅读 27
#include <iostream>
#include<algorithm>
#include<queue>
#include<unordered_map>
using namespace std;
queue<string>q;
int dx[]={1,-1,2,-2,3,-3};
unordered_map<string,int>d;
int bfs(string start,string end){
d[start]=0;
q.push(start);
while(q.size()){
auto t=q.front();
q.pop();
int distance=d[t];
if(t==end) return d[t];
int idx=t.find('*');
for(int i=0;i<6;i++){
int nidx=idx+dx[i];
if(nidx>=0&&nidx<t.size())&&&&&&&&&&&&&&&等于号不要忘记
{swap(t[idx],t[nidx]);
if(!d.count(t)){
d[t]=distance+1;
q.push(t);
}
swap(t[idx],t[nidx]);
}
}
}
return -1;
}
int main()
{
string start;
string end;
cin>>start>>end;
cout<<bfs(start,end)<<endl;
return 0;
}