@[Super_Dabubu](/user/546681) 普通bfs写过吗？
by 残阳如血 @ 2023-07-27 16:19:53
@[残阳如血](/user/726139) 写过呀，咋了？
by lcbridge @ 2023-07-27 16:22:59
我用您的代码这测出来6分（
by 残阳如血 @ 2023-07-27 16:24:16
@[残阳如血](/user/726139) 怎么改呢？
by lcbridge @ 2023-07-27 16:24:49
@[残阳如血](/user/726139)
```cpp
#include <bits/stdc++.h>
#define int long long
#define END 123804765
using namespace std;
const int N=1e5+5;
int I,walk[5][2]={{1,0},{-1,0},{0,1},{0,-1}};
map <int,int> ans;
map <int,int> S;
int To_int(int A[][4]){
int sum=0,w=1e8;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
sum+=A[i][j]*w;
w/=10;
}
}
return sum;
}
void bfs(){
queue <int> q;
q.push(I);
q.push(END);
ans[I]=0;
ans[END]=1;
S[I]=1;
S[END]=2;
while(!q.empty()){
int x=q.front();q.pop();
int xx=x,fx,fy,A[4][4];
//cout<<S[xx]<<' '<<E[xx]<<' '<<xx<<"\n";
string sx="";
while(xx){
sx+=(xx%10+'0');
xx/=10;
}
reverse(sx.begin(),sx.end());
int t=0;
//cout<<sx<<"\n";
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
A[i][j]=(sx[t++]-'0');
}
}
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
if(!A[i][j]){
fx=i,fy=j;
break;
}
}
}
//cout<<fx<<' '<<fy<<"\n";
for(int i=0;i<4;i++){
int nx=walk[i][0]+fx;
int ny=walk[i][1]+fy;
if(nx<1||nx>3||ny<1||ny>3)continue;
swap(A[fx][fy],A[nx][ny]);
int nb=To_int(A);
//cout<<nb<<' '<<x<<"\n";
if(S[nb]==S[x]){
swap(A[fx][fy],A[nx][ny]);
continue;
}
if(S[nb]+S[x]==3){
cout<<ans[x]+ans[nb];
exit(0);
}
S[nb]=S[x];
ans[nb]=ans[x]+1;
q.push(nb);
swap(A[fx][fy],A[nx][ny]);
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin>>I;
if(I==END){
cout<<0;
return 0;
}
bfs();
return 0;
}
```
by lcbridge @ 2023-07-27 16:25:23
@[残阳如血](/user/726139) 已经16分了
by lcbridge @ 2023-07-27 16:25:39
我有一个$A*$ 的，需要吗？
by 残阳如血 @ 2023-07-27 16:28:39
@[残阳如血](/user/726139) 你可以帮我改改BFS
by lcbridge @ 2023-07-27 16:29:45
@[Super_Dabubu](/user/546681) 可是 bfs 可以过啊 
by Light_az @ 2023-07-27 17:32:52
双向 bfs 实现挺麻烦的，之前被折磨过 
by Light_az @ 2023-07-27 17:33:17