八数码问题

八数码问题，广度优先搜索，数组记录最短路径，然后打印
2 6 4 1 3 7 0 5 8
8 1 5 7 3 6 4 0 2
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <set>
  6 #include <cmath>
  7 using namespace std;
  8 #define Max 10000000
  9 typedef int state[9];
 10 state st[Max],goal;        //记录中间状态，目标状态
 11 int dist[Max];    
 12 set<int> vis;
 13 int visit[Max];
 14 int fact[9];
 15 int lu[Max];        //记录路径
 16 int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
 17 void init()
 18 {
 19     /*vis.clear();
 20     memset(dist,0,sizeof(dist));*/
 21     fact[0]=1;
 22     for(int i=1;i<9;i++)
 23         fact[i]=fact[i-1]*i;
 24 }
 25 int try_to_insert(int x)
 26 {
 27     /*int sum=0,i;
 28     for(i=0;i<9;i++)
 29         sum=sum*10+st[x][i];
 30     if(vis.count(sum))
 31         return 0;
 32     vis.insert(sum);
 33     return 1;*/
 34     int code=0;
 35     for(int i=0;i<9;i++)
 36     {
 37         int cnt=0;
 38         for(int j=i+1;j<9;j++)
 39         {
 40             if(st[x][i]>st[x][j])
 41                 cnt++;
 42         }
 43         code+=fact[8 -i]*cnt;
 44     }
 45     if(visit[code])
 46         return 0;
 47     visit[code]=1;
 48     return 1;
 49 }
 50 int bfs()
 51 {
 52     init();
 53     int front=1,rear=2;
 54     int z,i,j;
 55     while(front<rear)
 56     {
 57         state& s=st[front];
 58         if(memcmp(goal,s,sizeof(s))==0)
 59             return front;            //此状态在队列中的位置
 60         for(z=0;z<9;z++)
 61             if(!s[z])
 62                 break;
 63         int x=z/3,y=z%3;
 64         int newx,newy,newz;
 65         for(i=0;i<4;i++)        //扩展新结点
 66         {
 67             newx=x+dx[i];
 68             newy=y+dy[i];
 69             newz=newx*3+newy;
 70             if(newx<3&&newx>=0&&newy>=0&&newy<3)
 71             {
 72                 state& t=st[rear];
 73                 memcpy(&t,&s,sizeof(s));
 74                 t[newz]=s[z];            //空格
 75                 t[z]=s[newz];
 76                 dist[rear]=dist[front]+1;
 77                 if(try_to_insert(rear))
 78                 {
 79                     rear++;
 80                     lu[rear]=front;
 81                 }
 82             }
 83         }
 84         front++;
 85     }
 86     return 0;
 87 }
 88 int main()
 89 {
 90     int i,j,ans;
 91     lu[2]=1;
 92     freopen("in.txt","r",stdin);
 93     for(i=0;i<9;i++)
 94     {
 95         cin>>st[1][i];
 96     }
 97     for(i=0;i<9;i++)
 98         cin>>goal[i];
 99     ans=bfs();
100     cout<<dist[ans]<<endl;
101     int k=ans;
102     while(k>0)
103     {
104         for(j=0;j<9;j++)
105             cout<<st[k][j]<<" ";
106         cout<<endl;
107         k=lu[k];
108     }
109 
110 }