【hdu1043 && poj 1077】八数码问题

题目大意：给你一个九宫格的初始状态（一个空格+数字1~8），让你按规则走变成目标状态（数字按顺序排序+空格在最后），如果有这样的解法输出其中一种少操作步骤解法，否则输出unsolvable。

解题思路：超级经典的题目，解法超级多（据说有八重解法，和乾坤大挪移一样的，越到后面说明你越厉害），本来属于弱菜，只能达到三重。

虽然上面两题题目是一样的，但是用的解法不一样，因为....蛋都碎了。

poj1077：康托展开+双向bfs（32ms）

数据比较弱，很多人都是用正向bfs水过去的，这里我用的是双向bfs，何谓双向bfs？简单的说就是起始状态和目标状态一起搜，轮着来。当在搜的过程中发现某个状态已经被另一不同开始状态搜过时，此时为最优解，即最优路径。双向bfs比单向bfs无论在时间上还是空间上都节省很多。

联想一下bfs是从某一个点向四周扩散的，给你看个图就理解了。

这里还要介绍一下如何保存状态：

方法1：0-8，总共也就9位数，我们可以对应它进行int压缩，比如格子数从左到右从上到下为 2 3 1 5 x 8 4 6 7 ，可以将它进行压缩为2 3 1 5 8 4 6 7 5（x空格在第5位放在个位对应数字5，其余的对应int数前8位数）。

方法2：9位数总共有9！个状态，可以利用到康托展开，何谓康托展开？比如数3 2 1 ，问你321在序列1 2 3全排列中是第几大，第一位是3，后面比它小的有1、2，则有2*2！，第二位数是2，后面比它小的有1，则有1*1！，加起来就是2*2！+1*1！=5，所以是第五大了。（具体：here）

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <queue>
  4 #include <algorithm>
  5 #include <cstring>
  6 using namespace std;
  7 
  8 const int maxn=366666;
  9 int visit1[maxn], visit2[maxn];
 10 int pp[9]= {1,1,2,6,24,120,720,5040,40430};
 11 int dir[4][2]= {0,1,0,-1,-1,0,1,0};
 12 char dd[4]= {'r','l','u','d'};
 13 int tp[maxn], st_aim, sd_aim;
 14 
 15 struct node
 16 {
 17     int pos0;
 18     int state;
 19     int s[9];
 20 };
 21 
 22 struct path
 23 {
 24     int pre;
 25     int dir;
 26 }path1[maxn], path2[maxn];
 27 
 28 int cantor(int ss[])
 29 {
 30     int sum=0;
 31     for(int i=0; i<9; i++)
 32     {
 33         int num=0;
 34         for(int j=i+1; j<9; j++)
 35             if(ss[j]<ss[i]) num++;
 36         sum+=num*pp[8-i];
 37     }
 38     return sum;
 39 }
 40 
 41 char change(char c)
 42 {
 43     if(c=='u') return 'd';
 44     else if(c=='d') return 'u';
 45     else if(c=='l') return 'r';
 46     else if(c=='r') return 'l';
 47 }
 48 
 49 void output1(int state)
 50 {
 51     int num=0;
 52     while(state!=st_aim) tp[num++]=path1[state].dir, state=path1[state].pre;
 53     for(int i=num-1; i>=0; i--) printf("%c",tp[i]);
 54 }
 55 
 56 void output2(int state)
 57 {
 58     while(state!=sd_aim) printf("%c",change(path2[state].dir)), state=path2[state].pre;
 59     puts("");
 60 }
 61 
 62 bool bfs(int ss[])
 63 {
 64     queue<node>p,q;
 65     node cur, tmp;
 66     memset(visit1,0,sizeof(visit1));
 67     memset(visit2,0,sizeof(visit2));
 68     for(int i=0; i<9; i++)
 69     {
 70         cur.s[i]=ss[i];
 71         if(ss[i]==0) cur.pos0=i;
 72     }
 73     cur.state=cantor(cur.s);
 74     q.push(cur);
 75     visit1[cur.state]=1, st_aim=cur.state;
 76     for(int i=0; i<8; i++) cur.s[i]=i+1;
 77     cur.s[8]=0, cur.pos0=8;
 78     cur.state=cantor(cur.s);
 79     p.push(cur);
 80     if(visit1[cur.state])  {  puts(""); return true; }
 81     visit2[cur.state]=1, sd_aim=cur.state;
 82     while(!q.empty()&&!p.empty())
 83     {
 84         if(!q.empty())
 85         {
 86             tmp=q.front();
 87             q.pop();
 88             for(int k=0; k<4; k++)
 89             {
 90                 int  x=tmp.pos0/3+dir[k][0];
 91                 int  y=tmp.pos0%3+dir[k][1];
 92                 if(x>=0&&x<=2&&y>=0&&y<=2)
 93                 {
 94                     for(int i=0; i<9; i++) cur.s[i]=tmp.s[i];
 95                     cur.pos0=3*x+y;
 96                     swap(cur.s[cur.pos0],cur.s[tmp.pos0]);
 97                     cur.state=cantor(cur.s);
 98                     if(visit2[cur.state])
 99                     {
100                         output1(tmp.state);
101                         printf("%c",dd[k]);
102                         output2(cur.state);
103                         return true;
104                     }
105                     if(!visit1[cur.state])
106                     {
107                         visit1[cur.state]=1;
108                         path1[cur.state].pre=tmp.state;
109                         path1[cur.state].dir=dd[k];
110                         q.push(cur);
111                     }
112                 }
113             }
114         }
115         if(!p.empty())
116         {
117             tmp=p.front();
118             p.pop();
119             for(int k=0; k<4; k++)
120             {
121                 int  x=tmp.pos0/3+dir[k][0];
122                 int  y=tmp.pos0%3+dir[k][1];
123                 if(x>=0&&x<=2&&y>=0&&y<=2)
124                 {
125                     for(int i=0; i<9; i++) cur.s[i]=tmp.s[i];
126                     cur.pos0=3*x+y;
127                     swap(cur.s[cur.pos0],cur.s[tmp.pos0]);
128                     cur.state=cantor(cur.s);
129                     if(visit1[cur.state])
130                     {
131                         output1(cur.state);
132                         printf("%c",change(dd[k]));
133                         output2(tmp.state);
134                         return true;
135                     }
136                     if(!visit2[cur.state])
137                     {
138                         visit2[cur.state]=1;
139                         path2[cur.state].pre=tmp.state;
140                         path2[cur.state].dir=dd[k];
141                         p.push(cur);
142                     }
143                 }
144             }
145         }
146     }
147     return false;
148 }
149 
150 int main()
151 {
152     char str[30];
153     int  s[10];
154     while(gets(str))
155     {
156         int num=0;
157         for(int i=0; str[i]; i++)
158         {
159             if(str[i]>='1'&&str[i]<='8') s[num++]=str[i]-'0';
160             else if(str[i]=='x') s[num++]=0;
161         }
162         bool ok=bfs(s);
163         if(!ok) puts("unsolvable");
164     }
165 }
166 // 1 2 3 4 x 6 7 5 8

hdu1043: 康托展开+逆序bfs（打表）（296ms）（为什么我写的双向bfs在这里过不了，难道是我写搓了？）

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cmath>
  4 #include <algorithm>
  5 #include <cstring>
  6 using namespace std;
  7 
  8 const int maxn=366666;
  9 int visit[maxn];
 10 int pp[9]= {1,1,2,6,24,120,720,5040,40430};
 11 int dir[4][2]= {0,1,0,-1,-1,0,1,0};
 12 char dd[4]= {'r','l','u','d'};
 13 string path[maxn];
 14 
 15 struct node
 16 {
 17     int pos0;
 18     int state;
 19     int s[9];
 20     string path;
 21 } que[maxn];
 22 
 23 int cantor(int ss[])
 24 {
 25     int sum=0;
 26     for(int i=0; i<9; i++)
 27     {
 28         int num=0;
 29         for(int j=i+1; j<9; j++)
 30             if(ss[j]<ss[i]) num++;
 31         sum+=num*pp[8-i];
 32     }
 33     return sum;
 34 }
 35 
 36 void bfs()
 37 {
 38     int l=0, h=0;
 39     node cur, tmp;
 40     memset(visit,0,sizeof(visit));
 41     for(int i=0; i<8; i++) cur.s[i]=i+1;
 42     cur.s[8]=0, cur.pos0=8;
 43     cur.path="";
 44     cur.state=cantor(cur.s);
 45     que[l++]=cur;
 46     visit[cur.state]=1;
 47     path[cur.state]=cur.path;
 48     while(l!=h)
 49     {
 50         tmp=que[h++];
 51         for(int k=0; k<4; k++)
 52         {
 53             int  x=tmp.pos0/3+dir[k][0];
 54             int  y=tmp.pos0%3+dir[k][1];
 55             if(x>=0&&x<=2&&y>=0&&y<=2)
 56             {
 57                 for(int i=0; i<9; i++) cur.s[i]=tmp.s[i];
 58                 cur.pos0=3*x+y;
 59                // cout << cur.pos0 << "---" << tmp.pos0 << "----" << cur.path << "---"<<dd[k]<<endl;
 60                 swap(cur.s[cur.pos0],cur.s[tmp.pos0]);
 61                 cur.state=cantor(cur.s);
 62                 if(!visit[cur.state])
 63                 {
 64                     cur.path=tmp.path+dd[k];
 65                     visit[cur.state]=1;
 66                     que[l++]=cur;
 67                     path[cur.state]=cur.path;
 68                 }
 69             }
 70         }
 71     }
 72 }
 73 
 74 void output(string s)
 75 {
 76     int len=s.size();
 77     for(int i=len; i>=0; i--)
 78     {
 79         if(s[i]=='u') printf("d");
 80         else if(s[i]=='d') printf("u");
 81         else if(s[i]=='l') printf("r");
 82         else if(s[i]=='r') printf("l");
 83     }
 84     puts("");
 85 }
 86 
 87 int main()
 88 {
 89     char str[30];
 90     int  s[10];
 91     bfs();
 92     while(gets(str))
 93     {
 94         int num=0;
 95         for(int i=0; str[i]; i++)
 96         {
 97             if(str[i]>='1'&&str[i]<='8') s[num++]=str[i]-'0';
 98             else if(str[i]=='x') s[num++]=0;
 99         }
100         int s_state=cantor(s);
101         if(!visit[s_state]) puts("unsolvable");
102         else output(path[s_state]);
103     }
104 }

因为此题太经典，所以在此占个坑，以后慢慢来攻破这八层境界（A*+IDA*+>>>>）。