【HDOJ】1043 Eight

这道题目最开始做的时候wa+TLE。后面知道需要状态压缩，最近A掉。并且练习一下各种搜索算法。

1. 逆向BFS+康拓展开。

 1 #include <iostream>
 2 #include <queue>
 3 #include <cstring>
 4 #include <string>
 5 #include <cstdio>
 6 using namespace std;
 7 
 8 #define N 9
 9 #define MAXNUM 362880
10 
11 typedef struct {
12     char map[N];
13     int xpos;
14     string path;
15 } node_st;
16 
17 int fact[N] = {1,1,2,6,24,120,720,5040,40320};
18 int direct[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
19 char rmove[4] = {'d','u','r','l'};
20 char visit[MAXNUM];
21 string rpath[MAXNUM];
22 
23 int cantor(node_st node) {
24     int i, j, cnt, val = 0;
25 
26     for (i=0; i<N; ++i) {
27         cnt = 0;
28         for (j=i+1; j<N; ++j) {
29             if (node.map[j] < node.map[i])
30                 ++cnt;
31         }
32         val += fact[N-1-i]*cnt;
33     }
34 
35     return val;
36 }
37 
38 void bfs() {
39     queue<node_st> que;
40     node_st node;
41     int i, x, y, t1, t2, can;
42 
43     for (i=1; i<N; ++i)
44         node.map[i-1] = '0' + i;
45     node.map[N-1] = 'x';
46     node.xpos = N-1;
47     memset(visit, 0, sizeof(visit));
48     visit[0] = 1;
49     que.push(node);
50 
51     while ( !que.empty() ) {
52         node = que.front();
53         que.pop();
54         t1 = node.xpos / 3;
55         t2 = node.xpos % 3;
56         for (i=0; i<4; ++i) {
57             x = t1 + direct[i][0];
58             y = t2 + direct[i][1];
59             if (x<0 || x>=3 || y<0 || y>=3)
60                 continue;
61             node_st tmp(node);
62             tmp.xpos = x*3+y;
63             tmp.map[node.xpos] = node.map[tmp.xpos];
64             tmp.map[tmp.xpos] = 'x';
65             can = cantor(tmp);
66             if ( !visit[can] ) {
67                 visit[can] = 1;
68                 tmp.path += rmove[i];
69                 rpath[can] = tmp.path;
70                 que.push(tmp);
71             }
72         }
73     }
74 }
75 
76 int main() {
77     node_st node;
78     int i, can;
79 
80     bfs();
81 
82     while (scanf("%c%*c", &node.map[0]) != EOF) {
83         for (i=1; i<N; ++i)
84             scanf("%c%*c", &node.map[i]);
85         can = cantor(node);
86         if ( visit[can] ) {
87             for (i=rpath[can].size()-1; i>=0; --i)
88                 printf("%c", rpath[can][i]);
89             printf("
");
90         } else {
91             printf("unsolvable
");
92         }
93     }
94 
95     return 0;
96 }

2. 双端BFS。注意逆序奇偶性相同才有解。

  1 #include <iostream>
  2 #include <queue>
  3 #include <string>
  4 #include <algorithm>
  5 #include <cstring>
  6 #include <cstdio>
  7 using namespace std;
  8 
  9 #define N 9
 10 #define MAXNUM 362880
 11 
 12 typedef struct {
 13     char map[N];
 14     int xpos;
 15     string path;
 16 } node_st;
 17 
 18 int fact[N]={1,1,2,6,24,120,720,5040,40320};
 19 int direct[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
 20 char move[4] = {'u','d','l','r'};
 21 char rmove[4] = {'d','u','r','l'};
 22 char visit[MAXNUM];
 23 bool flag;
 24 string paths[MAXNUM], fpath;
 25 queue<node_st> que, rque;
 26 
 27 
 28 inline int cantor(node_st node) {
 29     int i, j, cnt, val = 0;
 30 
 31     for (i=0; i<N; ++i) {
 32         cnt = 0;
 33         for (j=i+1; j<N; ++j)
 34             if (node.map[j] < node.map[i])
 35                 ++cnt;
 36         val += fact[N-1-i]*cnt;
 37     }
 38 
 39     return val;
 40 }
 41 
 42 inline bool invNum(node_st node) {
 43     int i, j, cnt = 0;
 44 
 45     for (i=0; i<N; ++i) {
 46         if (node.map[i] == 'x')
 47             continue;
 48         for (j=i-1; j>=0; --j)
 49             if (node.map[j]!='x' && node.map[j]>node.map[i])
 50                 ++cnt;
 51     }
 52 
 53     return cnt&1;
 54 }
 55 
 56 void bfs() {
 57     int x, y, can;
 58     node_st node = que.front();
 59     que.pop();
 60 
 61     for (int i=0; i<4; ++i) {
 62         x = node.xpos/3 + direct[i][0];
 63         y = node.xpos%3 + direct[i][1];
 64         if (x<0 || x>=3 || y<0 || y>=3)
 65             continue;
 66         node_st p(node);
 67         p.map[p.xpos] = node.map[x*3+y];
 68         p.xpos = x*3+y;
 69         p.map[p.xpos] = 'x';
 70         can = cantor(p);
 71         if (visit[can] == 1)
 72             continue;
 73         p.path += move[i];
 74         if (visit[can] == -1) {
 75             flag = false;
 76             reverse(paths[can].begin(), paths[can].end());
 77             fpath = p.path + paths[can];
 78             return ;
 79         }
 80         visit[can] = 1;
 81         paths[can] = p.path;
 82         que.push(p);
 83     }
 84 }
 85 
 86 void rbfs() {
 87     int x, y, can;
 88     node_st node = rque.front();
 89     rque.pop();
 90 
 91     for (int i=0; i<4; ++i) {
 92         x = node.xpos/3 + direct[i][0];
 93         y = node.xpos%3 + direct[i][1];
 94         if (x<0 || x>=3 || y<0 || y>=3)
 95             continue;
 96         node_st p(node);
 97         p.map[p.xpos] = node.map[x*3+y];
 98         p.xpos = x*3+y;
 99         p.map[p.xpos] = 'x';
100         can = cantor(p);
101         if (visit[can] == -1)
102             continue;
103         p.path += rmove[i];
104         if (visit[can] == 1) {
105             flag = false;
106             reverse(p.path.begin(), p.path.end());
107             fpath = paths[can] + p.path;
108         }
109         visit[can] = -1;
110         paths[can] = p.path;
111         rque.push(p);
112     }
113 }
114 
115 int main() {
116     node_st node, enode;
117     int i, n, can;
118 
119     for (i=1; i<N; ++i)
120         enode.map[i-1] = i + '0';
121     enode.map[N-1] = 'x';
122     enode.xpos = N-1;
123 
124     while (scanf("%c%*c", &node.map[0]) != EOF) {
125         for (i=0; i<N; ++i) {
126             if (i)
127                 scanf("%c%*c", &node.map[i]);
128             if (node.map[i] == 'x')
129                 node.xpos = i;
130         }
131         if ( invNum(node) ) {
132             printf("unsolvable
");
133             continue;
134         }
135         can = cantor(node);
136         if ( can == 0 ) {
137             printf("
");
138             continue;
139         }
140         while ( !que.empty() )
141             que.pop();
142         while ( !rque.empty() )
143             rque.pop();
144         memset(visit, 0, sizeof(visit));
145         flag = true;
146         rque.push(enode);
147         visit[0] = -1;
148         que.push(node);
149         visit[can] = 1;
150         while (flag) {
151             n = que.size();
152             while (flag && n--)
153                 bfs();
154             n = rque.size();
155             while (flag && n--)
156                 rbfs();
157         }
158         cout <<fpath<<endl;
159     }
160 
161     return 0;
162 }

3. A-star h函数为曼哈顿距离，必须用内联才不会TLE。

  1 #include <iostream>
  2 #include <queue>
  3 #include <stack>
  4 #include <string>
  5 #include <algorithm>
  6 #include <cstring>
  7 #include <cstdio>
  8 using namespace std;
  9 
 10 #define N 9
 11 #define MAXN 362880
 12 //#define myabs(x) ((x)>0) ? (x):(-(x))
 13 
 14 typedef struct node_st {
 15     char map[N];
 16     int xpos;
 17     int s, p;
 18     friend bool operator < (node_st a, node_st b) {
 19         return a.p > b.p;
 20     }
 21 } node_st;
 22 
 23 char visit[MAXN];
 24 int fact[N] = {1,1,2,6,24,120,720,5040,40320};
 25 int direct[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
 26 char move[4] = {'u', 'd', 'l', 'r'};
 27 int pre[MAXN], bcan;
 28 char op[MAXN];
 29 node_st beg;
 30 
 31 inline int cantor(node_st node) {
 32     int i, j, cnt, val = 0;
 33 
 34     for (i=0; i<N; ++i) {
 35         cnt = 0;
 36         for (j=i+1; j<N; ++j)
 37             if (node.map[j] < node.map[i])
 38                 ++cnt;
 39         val += fact[N-1-i]*cnt;
 40     }
 41 
 42     return val;
 43 }
 44 
 45 inline myabs(int x) {
 46     return (x>0) ? x:-x;
 47 }
 48 
 49 inline int h(node_st node) {
 50     int tmp, val = 0;
 51 
 52     for (int i=0; i<N; ++i) {
 53         if (node.map[i] == 'x') continue;
 54         tmp = node.map[i] - '1';
 55         val += myabs(tmp/3-i/3) + myabs(tmp%3-i%3);
 56     }
 57 
 58     return val;
 59 }
 60 
 61 inline bool invNum(node_st node) {
 62     int i, j, cnt = 0;
 63 
 64     for (i=0; i<N; ++i) {
 65         if (node.map[i] == 'x') continue;
 66         for (j=i-1; j>=0; --j)
 67             if (node.map[j]!='x' && node.map[j]>node.map[i])
 68                 ++cnt;
 69     }
 70 
 71     return cnt&1;
 72 }
 73 
 74 void bfs() {
 75     priority_queue<node_st> que;
 76     node_st node;
 77     int i, t1, t2, x, y, can, pcan;
 78 
 79     que.push(beg);
 80     memset(visit, 0, sizeof(visit));
 81     visit[bcan] = 1;
 82 
 83     while ( !que.empty() ) {
 84         node = que.top();
 85         que.pop();
 86         t1 = node.xpos / 3;
 87         t2 = node.xpos % 3;
 88         pcan = cantor(node);
 89         for (i=0; i<4; ++i) {
 90             x = t1 + direct[i][0];
 91             y = t2 + direct[i][1];
 92             if (x<0 || x>=3 || y<0 || y>=3)
 93                 continue;
 94             node_st p(node);
 95             p.map[node.xpos] = p.map[x*3+y];
 96             p.xpos = x*3+y;
 97             p.map[p.xpos] = 'x';
 98             can = cantor(p);
 99             if (visit[can])
100                 continue;
101             visit[can] = 1;
102             ++p.s;
103             p.p = p.s + h(p);
104             pre[can] = pcan;
105             op[can] = move[i];
106             if (can == 0)
107                 return ;
108             que.push(p);
109         }
110     }
111 }
112 
113 int main() {
114     int i, k;
115     stack<char> st;
116 
117     while (scanf("%c%*c", &beg.map[0]) != EOF) {
118         for (i=0; i<N; ++i) {
119             if (i)
120                 scanf("%c%*c", &beg.map[i]);
121             if (beg.map[i] == 'x')
122                 beg.xpos = i;
123         }
124         beg.s = 0;
125         beg.p = h(beg);
126         if ( invNum(beg) ) {
127             printf("unsolvable
");
128             continue;
129         }
130         bcan = cantor(beg);
131         if (bcan == 0) {
132             printf("
");
133             continue;
134         }
135         bfs();
136         k = 0;
137         while (k != bcan) {
138             st.push(op[k]);
139             k = pre[k];
140         }
141 
142         while ( !st.empty() ) {
143             printf("%c", st.top());
144             st.pop();
145         }
146         printf("
");
147     }
148     return 0;
149 }

4. IDA*，该算法其实是迭代dfs。H函数还是曼哈顿距离。

  1 #include <iostream>
  2 #include <string>
  3 #include <cstdio>
  4 #include <cstring>
  5 using namespace std;
  6 
  7 #define N       9
  8 #define MAXN    362880
  9 
 10 typedef struct {
 11     char map[N];
 12     int xpos;
 13 } node_st;
 14 
 15 int fact[N] = {1,1,2,6,24,120,720,5040,40320};
 16 int direct[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
 17 char move[4] = {'u', 'd', 'l', 'r'};
 18 char visit[MAXN];
 19 char op[MAXN];
 20 int deep;
 21 bool flag;
 22 node_st beg;
 23 
 24 inline int cantor(node_st node) {
 25     int i, j, cnt, val = 0;
 26 
 27     for (i=0; i<N; ++i) {
 28         cnt = 0;
 29         for (j=i+1; j<N; ++j)
 30             if (node.map[j] < node.map[i])
 31                 ++cnt;
 32         val += fact[N-1-i]*cnt;
 33     }
 34 
 35     return val;
 36 }
 37 
 38 inline bool invNum(node_st node) {
 39     int i, j, cnt = 0;
 40 
 41     for (i=0; i<N; ++i) {
 42         if (node.map[i] == 'x') continue;
 43         for (j=i-1; j>=0; --j)
 44             if (node.map[j]!='x' && node.map[j]>node.map[i])
 45                 ++cnt;
 46     }
 47 
 48     return cnt&1;
 49 }
 50 
 51 inline int myabs(int x) {
 52     return (x<0) ? -x:x;
 53 }
 54 
 55 inline int h(node_st node) {
 56     int i, tmp, val = 0;
 57 
 58     for (i=0; i<N; ++i) {
 59         if (node.map[i] == 'x') continue;
 60         tmp = node.map[i] - '1';
 61         val += myabs(tmp/3-i/3) + myabs(tmp%3-i%3);
 62     }
 63 
 64     return val;
 65 }
 66 
 67 void dfs(int d) {
 68     int i, t1, t2, x, y, can;
 69 
 70     t1 = h(beg);
 71     if (t1 == 0) {
 72         flag = false;
 73         return ;
 74     }
 75     if (t1+d > deep)
 76         return ;
 77     t1 = beg.xpos / 3;
 78     t2 = beg.xpos % 3;
 79     for (i=0; i<4; ++i) {
 80         x = t1 + direct[i][0];
 81         y = t2 + direct[i][1];
 82         if (x<0 || x>=3 || y<0 || y>=3)
 83             continue;
 84         node_st p(beg), org(beg);
 85         p.map[p.xpos] = p.map[x*3+y];
 86         p.xpos = x*3+y;
 87         p.map[p.xpos] = 'x';
 88         can = cantor(p);
 89         if (visit[can]) continue;
 90         visit[can] = 1;
 91         op[d] = move[i];
 92         beg = p;
 93         dfs(d+1);
 94         if ( !flag )
 95             return ;
 96         beg = org;
 97         visit[can] = 0;
 98     }
 99 }
100 
101 int main() {
102     int i;
103 
104     while (scanf("%c%*c", &beg.map[0]) != EOF) {
105         for (i=0; i<N; ++i) {
106             if (i)
107                 scanf("%c%*c", &beg.map[i]);
108             if (beg.map[i] == 'x')
109                 beg.xpos = i;
110         }
111         if ( invNum(beg) ) {
112             printf("unsolvable
");
113             continue;
114         }
115         memset(visit, 0, sizeof(visit));
116         memset(op, 0, sizeof(op));
117         i = cantor(beg);
118         visit[i] = 1;
119         deep = h(beg);
120         flag = true;
121         while (flag) {
122             ++deep;
123             dfs(0);
124             //printf("%d
", deep);
125         }
126 
127         i = 0;
128         while ( op[i] )
129             printf("%c", op[i++]);
130         printf("
");
131     }
132 
133     return 0;
134 }