POJ1077 Eight —— 反向BFS

主页面：http://www.cnblogs.com/DOLFAMINGO/p/7538588.html

代码一：以数组充当队列，利用结构体中的pre追溯上一个状态在数组（队列）中的下标：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 #define ms(a,b) memset((a),(b),sizeof((a)))

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 1e6+;

 struct node

 {

     int status;

     int s[];

     int loc;

     char op;

     int pre;    //pre为上一个操作在队列中的下标，用于输出路径

 };

 int vis[MAXN], fac[] = { , , , , , , , , };

 int dir[][] = { ,,,-,  ,, -,  };

 char op[] = {'l', 'r', 'u', 'd'  };    //由于反向操作，则方向应该反过来

 int id[MAXN];

 int cantor(int s[])     //获得哈希函数值

 {

     int sum = ;

     for(int i = ; i<; i++)

     {

         int num = ;

         for(int j = i+; j<; j++)

             if(s[j]<s[i])

                 num++;

         sum += num*fac[-i];

     }

     return sum+;

 }

 node que[MAXN];

 int front, rear;

 void bfs()

 {

     ms(vis, );

     front = rear = ;

     node now, tmp;

     for(int i = ; i<; i++)    //初始状态为123456789

         now.s[i] = i+;

     now.loc = ;

     now.status = cantor(now.s);

     vis[now.status] = ;

     id[now.status] = rear;   //初始状态在队列中的下标

     que[rear++] = now;

     while(front!=rear)

     {

         now = que[front++];

         int x = now.loc/;

         int y = now.loc%;

         for(int i = ; i<; i++)

         {

             int xx = x + dir[i][];

             int yy = y + dir[i][];

             if(xx>= && xx<= && yy>= && yy<=)

             {

                 tmp = now;

                 tmp.s[x*+y] = tmp.s[xx*+yy];

                 tmp.s[xx*+yy] = ;

                 tmp.status = cantor(tmp.s);

                 if(!vis[tmp.status])

                 {

                     vis[tmp.status] = ;

                     tmp.loc = xx*+yy;

                     tmp.op = op[i];

                     tmp.pre = front-;

                     id[tmp.status] = rear;

                     que[rear++] = tmp;

                 }

             }

         }

     }

 }

 void Print(int i)

 {

     if(i==) return;    //队列下标为0的时候为初始状态， 应返回

     putchar(que[i].op); //输出操作

     Print(que[i].pre);  //访问BFS的上一步，但因为是反向BFS，所以对于答案来说是下一步，应放在putchar后面

 }

 int main()

 {

     bfs();//反向bfs，预处理所有情况。然后在访问的时候直接输出路径

     char str[];

     while(gets(str))

     {

         node aim;

         int cnt = ;

         for(int i = ; str[i]; i++)

         {

             if(str[i]==' ') continue;

             if(str[i]=='x') aim.s[cnt] = , aim.loc = cnt++;

             else  aim.s[cnt++] = str[i]-'';

         }

         aim.status = cantor(aim.s);

         if(!vis[aim.status])

             puts("unsolvable");

         else

             Print(id[aim.status]), putchar('\n');

     }

 }

代码二（推荐）：把pre和path放在结构体外，利用当前状态status追溯上一个状态status：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 #define ms(a,b) memset((a),(b),sizeof((a)))

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 1e6+;

 struct node

 {

     int status;

     int s[];

     int loc;

 };

 int vis[MAXN], fac[] = { , , , , , , , , };

 int dir[][] = { ,,,-,  ,, -,  };

 char op[] = {'l', 'r', 'u', 'd'  };    //由于反向操作，则方向应该反过来

 char path[MAXN];

 int pre[MAXN];

 int cantor(int s[])     //获得哈希函数值

 {

     int sum = ;

     for(int i = ; i<; i++)

     {

         int num = ;

         for(int j = i+; j<; j++)

             if(s[j]<s[i])

                 num++;

         sum += num*fac[-i];

     }

     return sum+;

 }

 queue<node>que;

 void bfs()

 {

     ms(vis, );

     while(!que.empty()) que.pop();

     node now, tmp;

     for(int i = ; i<; i++)    //初始状态为123456789

         now.s[i] = i+;

     now.loc = ;

     now.status = cantor(now.s);

     vis[now.status] = ;

     pre[now.status] = -;

     que.push(now);

     while(!que.empty())

     {

         now = que.front();

         que.pop();

         int x = now.loc/;

         int y = now.loc%;

         for(int i = ; i<; i++)

         {

             int xx = x + dir[i][];

             int yy = y + dir[i][];

             if(xx>= && xx<= && yy>= && yy<=)

             {

                 tmp = now;

                 tmp.s[x*+y] = tmp.s[xx*+yy];

                 tmp.s[xx*+yy] = ;

                 tmp.status = cantor(tmp.s);

                 if(!vis[tmp.status])

                 {

                     vis[tmp.status] = ;

                     tmp.loc = xx*+yy;

                     path[tmp.status] = op[i];

                     pre[tmp.status] = now.status;

                     que.push(tmp);

                 }

             }

         }

     }

 }

 void Print(int status)

 {

     if(pre[status]==-) return;

     putchar(path[status]);

     Print(pre[status]);

 }

 int main()

 {

     bfs();//反向bfs，预处理所有情况。然后在访问的时候直接输出路径

     char str[];

     while(gets(str))

     {

         node aim;

         int cnt = ;

         for(int i = ; str[i]; i++)

         {

             if(str[i]==' ') continue;

             if(str[i]=='x') aim.s[cnt] = , aim.loc = cnt++;

             else  aim.s[cnt++] = str[i]-'';

         }

         aim.status = cantor(aim.s);

         if(!vis[aim.status])

             puts("unsolvable");

         else

             Print(aim.status), putchar('\n');

     }

 }