哈哈,经过23分钟的奋斗,终于AC了这道题。
为了不让me的贴子太冷清,me来也。
1. if(x<0||x>2||y<0||y>2)continue;**22行**改为 **if(xx<0||xx>2||yy<0||yy>2)continue;**
1. int xx=x+dx[i];
int yy=y+dy[i];**20,21行**改为**int xx=x+dx[j];
int yy=y+dy[j];**
------------
代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
string S="123804765",ss;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int bfs(string s){
if(s==S)return 0;
map<string,bool>v;
v[s]=1;
queue<pair<string,long long> >que;
que.push({s,0});
while(que.size()){
string a=que.front().first;
long long b=que.front().second;
que.pop();
for(int i=0;i<9;i++){
if(a[i]=='0'){
int x=i/3,y=i%3;
for(int j=0;j<4;j++){
int xx=x+dx[j];
int yy=y+dy[j];
if(xx<0||xx>2||yy<0||yy>2)continue;
int k=xx*3+yy;
string Ss=a;
swap(Ss[i],Ss[k]);
if(Ss==S)return b+1;
if(v[Ss]==0){
v[Ss]=1;
que.push({Ss,b+1});
}
}
}
}
}
}
int main(){
cin>>ss;
cout<<bfs(ss);
return 0;
}
``````
BFS做法
by Szy0720 @ 2023-08-26 16:09:51