蓝桥打卡-6-九宫重拍(八数码)
作者:
因为yxc爱上编程
,
2024-04-07 10:46:24
,
所有人可见
,
阅读 26
#include <iostream>
#include<algorithm>
#include<unordered_map>
#include<queue>
using namespace std;
unordered_map<string,int>d;
queue<string>q;
int bfs(string start,string end){
q.push(start);
d[start]=0;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
while(q.size()){
auto t=q.front();
q.pop();
int distance=d[t];
if(t==end)
return distance;
int idx=t.find('.');
int a=idx/3;
int b=idx%3;
for(int i=0;i<4;i++){
int ax=a+dx[i];
int bx=b+dy[i];
if(0<=ax&&ax<3&&0<=bx&&bx<3){
swap(t[idx],t[ax*3+bx]);
if(!d.count(t))
{
d[t]=distance+1;
q.push(t);
}
swap(t[idx],t[ax*3+bx]);
}
}
}
return -1;
}
int main()
{
string start;
string end;
cin>>start>>end;
cout<<bfs(start,end)<<endl;
return 0;
}
这些题在哪里弄的呀
蓝桥官网就有