双向 BFS
原来双向 BFS 是这样的: 终止状态与起始状态同时入队, 进行搜索, 只不过状态标记不一样而已, 本题状态使用 map 来存储
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstdlib>
- #include<queue>
- #include<map>
- #include<cmath>
- using namespace std;
- int g=123804765,a[10][10],n;
- int dx[]= {0,0,1,-1},
- dy[]= {1,-1,0,0};
- queue<int>Q;
- map<int,int>v,ans;
- void slove() {
- if(n==g) {
- printf("0");
- exit(0);
- }
- Q.push(n),Q.push(g);// 起始状态与终止状态同时入队
- ans[n]=0,ans[g]=1;
- v[g]=2,v[n]=1;
- while(!Q.empty()) {
- int now,cur=Q.front();
- Q.pop();
- now=cur;
- int x,y;
- for(int i=3; i>=1; i--)
- for(int j=3; j>=1; j--) {
- a[i][j]=now%10,now/=10;
- if(!a[i][j]) x=i,y=j;
- }
- for(int i=0; i<4; i++) {
- int tx=x+dx[i],ty=y+dy[i];
- if(tx<1||tx>3||ty>3||ty<1) continue;
- swap(a[tx][ty],a[x][y]);
- now=0;
- for(int p=1; p<=3; p++)
- for(int k=1; k<=3; k++)
- now=now*10+a[p][k];
- if(v[now]==v[cur]) {
- swap(a[tx][ty],a[x][y]);
- continue;
- }
- if(v[now]+v[cur]==3) {
- printf("%d\n",ans[now]+ans[cur]);
- exit(0);
- }
- ans[now]=ans[cur]+1;
- v[now]=v[cur];
- Q.push(now);
- swap(a[tx][ty],a[x][y]);
- }
- }
- }
- int main() {
- scanf("%d",&n);
- slove();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2776307.html