「 Luogu P1379 」 八数码难题

# 解题思路

这题不难，主要就是考虑如何判重，如果直接在 $9$ 个位置上都比较一遍的话。你会得到下面的好成绩

所以考虑另一种方法：

将九个位置压成一个整数，并且因为只有九个数，所以不会超出 $int$，用 $set$ 判重，写一个 BFS 就过了

 

# 附上代码

#include<iostream> #include<cstdio> #include<queue> #include<set> using namespace std; struct node{ int map,zerox,zeroy,step; }; int pos=123804765; queue<node>P; set<int>S; int dx[7]={0,0,1,-1}; int dy[7]={1,-1,0,0}; void bfs(node now) { while(!P.empty()) { node now=P.front(); P.pop(); int map=now.map,x=now.zerox,y=now.zeroy,step=now.step; if(map==pos) { printf("%d",step); return ; } int nxt[5][5],k=map; for(int i=0;i<4;i++) { int xx=dx[i]+x,yy=dy[i]+y; if(xx>0&&xx<4&&yy>0&&yy<4) { k=map; for(int i=3;i>=1;i--) for(int j=3;j>=1;j--) nxt[i][j]=k%10,k/=10; nxt[x][y]=nxt[xx][yy],nxt[xx][yy]=0; int ps=0,h[15],o[15]; for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) ps=ps*10+nxt[i][j],h[nxt[i][j]]=i,o[nxt[i][j]]=j; if(!S.count(ps)) { S.insert(ps); P.push((node){ps,h[0],o[0],step+1}); } } } } } int main() { char p; int m=0,x0,y0; //scanf("%d",m); for(int i=1;i<=3;i++) { for(int j=1;j<=3;j++) { cin>>p; m=(p-'0')+m*10; if(p=='0') x0=i,y0=j; } } S.insert(m); P.push((node){m,x0,y0,0}); bfs(P.front()); }

 

转载于:https://www.cnblogs.com/bljfy/p/9625572.html

相关资源：遗传算法八数码