把最近遇到的搜索好题列一下（推荐做做）。
http://acm.pku.edu.cn/JudgeOnline/problem?id=2286
The Rotation Game
迭代深搜，中等难度。
一开始用广搜做，结果MLE（当然有可能程序写错），改成迭代深搜后，因为不用考虑判重，不用写状态压缩，程序变的特别简单，再加上一个剪枝后就过了。
剪枝：（8 - 中间8个格最多的数字的个数）> 剩余步数，则剪枝
POJ 2286
1 //2286_TheRotationGame ~ alpc02
2 #include <algorithm>
3 using namespace std;
4
5 const int N = 24;
6 const int L = 60;
7
8 int to[8][7] =
9 {
10 {0,2,6,11,15,20,22},
11 {1,3,8,12,17,21,23},
12 {10,9,8,7,6,5,4},
13 {19,18,17,16,15,14,13},
14 {23,21,17,12,8,3,1},
15 {22,20,15,11,6,2,0},
16 {13,14,15,16,17,18,19},
17 {4,5,6,7,8,9,10},
18 };
19 int center[8] = {6,7,8,11,12,15,16,17};
20
21 int a[N];
22
23 int centernum;
24 char path[L];
25 int len;
26
27 int Max(int a, int b) {return a>b?a:b;}
28 int check()
29 {
30 int i, c[4] = {0};
31 for(i=0; i<8; i++)
32 c[a[center[i]]]++;
33 return 8 - Max(c[1], Max(c[2], c[3]));
34 }
35 void go(int *b, int *t)
36 {
37 int i, temp;
38 temp = b[t[0]];
39 for(i=0; i<6; i++)
40 b[t[i]] = b[t[i+1]];
41 b[t[6]] = temp;
42 }
43 bool dfs(int k) {
44 int chk = check();
45 if(chk + k > len)
46 return false;
47 if(k == len) {
48 centernum = a[center[0]];
49 return true;
50 }
51 int t, b[N];
52 memcpy(b, a, sizeof(a));
53 for(t=0; t<8; t++) {
54 memcpy (a, b, sizeof(b));
55 go(a, to[t]);
56 if(dfs(k+1)) {
57 path[k] = 'A' + t;
58 return true;
59 }
60 }
61 memcpy(a, b, sizeof(b));
62 return false;
63 }
64 void solve() {
65 len = 0;
66 while(!dfs(0))
67 len++;
68 path[len] = 0;
69 }
70 bool input() {
71 int i;
72 scanf("%d", a+0);
73 if(a[0] == 0)
74 return false;
75 for(i=1; i<N; i++)
76 scanf("%d", a+i);
77 return true;
78 }
79
80 int main()
81 {
82 while(input()) {
83 solve();
84 if(len == 0)
85 printf("No moves needed\n");
86 else
87 printf("%s\n",path);
88 printf("%d\n", centernum);
89 }
90 return 0;
91 }称之为广搜，可这题真的是不那么好做啊。
一开始，广搜，TLE；然后双广，TLE；然后A*，TLE，当然有可能启发函数太次了。
最后请教
oyjpArt，才明白有那么猛的的算法。
大概思路是把所有操作分两类，一类是置换类，就是只是交换数字位置、移动光标位置，二类是加减类，就是对每个数字加1减1。
然后广搜也是分两步，先搜所有的置换，再“搜”所有的加减。
1、先说第二步，“搜”加减，很简单，每个数字相差几就是几步，加起来就是最小步数。
2、第一个搜，要记录置换的当前状态，光标状态，还有光标曾经过的数字的初始位置（用6位2进制存储，记录这个意思就是说只要经过的数字，以后就允许加减，一气呵成）
。。。写不明白
POJ 1184
1 //1184 聪明的打字员 ~ alpc02
2 #include <queue>
3 #include <algorithm>
4 using namespace std;
5
6 const int INF = 123456;
7 const int N = 46656;
8
9 int v[6];
10 int pow[6];
11 int to[6][6];
12 bool f[N][6][64] = {{{0}}};
13
14 int st[6], ed[6], a[6];
15
16 int Min(int a, int b) { return a<b ? a:b;}
17 void go(int s, int pos, int pass, int &ss, int &ppos, int &ppass, int t) {
18 ss = s;
19 ppos = pos;
20 ppass = pass;
21 switch(t) {
22 case 0:
23 if(ppos != 0) {
24 ppos--;
25 ppass |= pow[a[ppos]];
26 }
27 return;
28 case 1:
29 if(ppos != 5) {
30 ppos++;
31 ppass |= pow[a[ppos]];
32 }
33 return;
34 case 2:
35 ppass |= pow[a[0]];
36 ss += to[0][ppos] * (a[ppos] - a[0]);
37 return;
38 case 3:
39 ppass |= pow[a[5]];
40 ss += to[5][ppos] * (a[ppos] - a[5]);
41 return;
42 }
43 }
44 int dis(int *a, int pass) {
45 int i, ans = 0;
46 for(i=0; i<6; i++) {
47 if(st[a[i]] != ed[i]) {
48 if(pass & pow[a[i]]) {
49 ans += abs(st[a[i]] - ed[i]);
50 }
51 else {
52 return INF;
53 }
54 }
55 }
56 return ans;
57 }
58
59 void cal(int *a, int s, int k) {
60 int i;
61 for(i=5; i>=0; i--) {
62 a[i] = s % k;
63 s /= k;
64 }
65 }
66 struct node {
67 int s, pos, g, pass; //组合数状态，当前光标，步数，光标路过的点
68 node() {}
69 node(int ss, int ppos, int ppass, int gg) : s(ss), pos(ppos), pass(ppass), g(gg) {}
70 };
71
72 int solve() {
73 queue <node> myq;
74 node now;
75 int s, pos, pass, g;
76 int ss, ppos, ppass, gg;
77 int t;
78 int ans = INF;
79
80 myq.push(node(1865, 0, pow[0], 0));
81 f[1865][0][1] = true;
82
83 while(!myq.empty()) {
84 now = myq.front();
85 myq.pop();
86 g = now.g;
87 if(g >= ans) {
88 continue;
89 }
90
91 s = now.s;
92 pos = now.pos;
93 pass = now.pass;
94
95 cal(a, s, 6);
96
97 ans = Min(ans, dis(a, pass) + g);
98
99 gg = g + 1;
100
101 for(t=0; t<4; t++) {
102 go(s, pos, pass, ss, ppos, ppass, t);
103 if(!f[ss][ppos][ppass]) {
104 f[ss][ppos][ppass] = true;
105 myq.push(node(ss, ppos, ppass, gg));
106 }
107 }
108 }
109 return ans;
110 }
111
112 void init() {
113 int i, j;
114 v[5] = pow[5] = 1;
115 for(i=4; i>=0; i--) {
116 v[i] = v[i+1] * 6;
117 pow[i] = pow[i+1] * 2;
118 }
119 for(i=0; i<6; i++) {
120 for(j=0; j<6; j++) {
121 to[i][j] = v[i] - v[j];
122 }
123 }
124 }
125 int main() {
126 init();
127 int stt, edd;
128 scanf("%d %d", &stt, &edd);
129 cal(st, stt, 10);
130 cal(ed, edd, 10);
131 printf("%d\n", solve());
132 return 0;
133 }
http://acm.pku.edu.cn/JudgeOnline/problem?id=1376Robot广搜，容易。
后来加一个启发函数进去，是这样定义的：H(n) = 到目标横向距离 / 3 + 到目标纵向距离 / 3 ，除以3是因为一步可以走3个格子，结果比原来的还要慢。
POJ 1376
1 //1376_ Robot ~ alpc02
2 #include <queue>
3 using namespace std;
4
5 int n,m;
6 int bi, bj, bt, ei, ej;
7 bool mp[55][55];
8 bool f[55][55][4];
9
10 bool input ()
11 {
12 scanf ("%d %d", &m, &n);
13 int i, j, k;
14 memset (mp, true, sizeof(mp));
15 if (m == 0 && n == 0) return false;
16 for (i=1; i<=m; i++)
17 for (j=1; j<=n; j++)
18 {
19 scanf ("%d", &k);
20 if (k == 1)
21 mp[i][j] = mp[i-1][j] = mp[i][j-1] = mp[i-1][j-1] = false;
22 }
23 scanf ("%d %d %d %d", &bi, &bj, &ei, &ej);
24 char ts[10];
25 scanf ("%s", ts);
26 if (ts[0] == 'n')
27 bt = 0;
28 if (ts[0] == 'e')
29 bt = 1;
30 if (ts[0] == 's')
31 bt = 2;
32 if (ts[0] == 'w')
33 bt = 3;
34 return true;
35 }
36
37 struct typ
38 {
39 int i,j,t,s;
40 typ (){}
41 typ (int ii, int jj, int tt, int ss):i(ii),j(jj),t(tt),s(ss){}
42 };
43 int ti[] = {-1,0,1,0};
44 int tj[] = {0,1,0,-1};
45 int solve ()
46 {
47 memset (f, false, sizeof(f));
48 queue <typ> myq;
49
50 myq.push (typ(bi,bj,bt,0));
51 f[bi][bj][bt] = true;
52 typ now;
53
54 int i,j,ii,jj,t,s,k;
55 while (!myq.empty ())
56 {
57 now = myq.front ();
58 myq.pop ();
59 i = now.i;
60 j = now.j;
61 t = now.t;
62 s = now.s;
63 if (i==ei && j==ej)
64 return s;
65 for (k=1; k<=3; k++)
66 {
67 ii = i+ti[t]*k;
68 jj = j+tj[t]*k;
69 if (!(ii>0 && ii<m && jj>0 && jj<n && mp[ii][jj]))
70 break;
71 if (!f[ii][jj][t])
72 {
73 f[ii][jj][t] = true;
74 myq.push (typ(ii,jj,t,s+1));
75 }
76 }
77 if (!f[i][j][(t+1)%4])
78 {
79 f[i][j][(t+1)%4] = true;
80 myq.push (typ(i,j,(t+1)%4,s+1));
81 }
82 if (!f[i][j][(t+3)%4])
83 {
84 f[i][j][(t+3)%4] = true;
85 myq.push (typ(i,j,(t+3)%4,s+1));
86 }
87 }
88 return -1;
89 }
90
91 int main()
92 {
93 while (input ())
94 {
95 printf ("%d\n", solve ());
96 }
97 return 0;
98 }
http://acm.pku.edu.cn/JudgeOnline/problem?id=2449Remmarguts' Date
求S到T的K短路，数据量N=1000，M=100000，K=1000。较难
1、用优先队列做广搜，当然跟一般广搜不一样，每个点允许k次出列，第k次出列的T点即是解。（理论上可行，但是实际确MLE超内存）
2、加入启发式函数H——到T的最短距离，传说中的A*就是这样来的。显然 这个最短距离 < i 短距离，满足条件，重要的是事实证明效果很不错。
参考：
http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1144
POJ 2449
1 //2449_kShortestRoute ~ alpc02
2 #include <queue>
3 #include <algorithm>
4 using namespace std;
5
6 #define Min(a,b) (a) < (b) ? (a) : (b)
7 #define INF 12345678
8
9 const int N = 1010;
10 const int M = 100010;
11
12 int n,m,s,t,k;
13 int head[N];
14 int other[M], next[M], len[M];
15 int head_rev[N];
16 int other_rev[M], next_rev[M];
17
18 int cnt[N];
19 int dis[N];
20 bool f[N];
21
22 void add (int a, int b, int ln)
23 {
24 other[m] = b;
25 next[m] = head[a];
26 head[a] = m;
27
28 other_rev[m] = a;
29 next_rev[m] = head_rev[b];
30 head_rev[b] = m;
31
32 len[m++] = ln;
33 }
34 void input ()
35 {
36 int i, a, b, ln;
37 scanf ("%d %d", &n, &m);
38 memset (head, -1, sizeof(head));
39 memset (head_rev, -1, sizeof(head_rev));
40 i = m;
41 m = 0;
42 while (i--)
43 {
44 scanf ("%d %d %d", &a, &b, &ln);
45 add (a, b, ln);
46 }
47 scanf ("%d %d %d", &s, &t, &k);
48 }
49
50 void dij ()
51 {
52 int i, j;
53 memset (f, false, sizeof(f));
54 for (i=1; i<=n; i++)
55 dis[i] = INF;
56 dis[t] = 0;
57 while (true)
58 {
59 i = -1;
60 for (j=1; j<=n; j++)
61 if (!f[j] && (i == -1 || dis[j] < dis[i]))
62 i = j;
63 if (i == -1) break;
64 f[i] = true;
65 for (j = head_rev[i]; j!=-1; j=next_rev[j])
66 dis[other_rev[j]] = Min (dis[other_rev[j]], dis[i] + len[j]);
67 }
68 }
69
70 struct type
71 {
72 int i,ln;
73 type (){}
74 type (int ii,int ll):i(ii), ln(ll){}
75 };
76 bool operator < (const type &a, const type &b)
77 {
78 return (a.ln + dis[a.i]) > (b.ln + dis[b.i]);
79 }
80 int solve ()
81 {
82 dij ();
83
84 memset (cnt, 0, sizeof (cnt));
85 int i,j,ii,ln;
86
87 priority_queue <type> myq;
88 type now;
89
90 myq.push (type (s,0));
91 cnt[s] = -1;
92 while (!myq.empty ())
93 {
94 now = myq.top ();
95 myq.pop ();
96 i = now.i;
97 if (++cnt[i] > k)
98 continue;
99 if (i == t && cnt[t] == k)
100 return now.ln;
101
102 ln = now.ln;
103
104 for (j=head[i]; j!=-1; j=next[j])
105 {
106 ii = other[j];
107 if (cnt[ii] < k)
108 myq.push (type (ii, ln+len[j]));
109 }
110 }
111 return -1;
112 }
113
114 int main ()
115 {
116 input ();
117 printf ("%d\n", solve ());
118 return 0;
119 }
http://acm.pku.edu.cn/JudgeOnline/problem?id=1011 Sticks剪枝好题，中等难度
两个强剪枝
1、如果长度为5的木棍刚好能满足当前块，就没必要尝试用2+3的木棍
2、如果当前块为空，则可指定任意一根木棍放入其内，也没必要尝试其他木棍
POJ 1011
1 //1011_Sticks ~ alpc02
2 #include <stdio.h>
3 #include <string.h>
4 #include <algorithm>
5 using namespace std;
6
7 const int M=70;
8
9 int n,m,len;
10 int a[M];
11 bool f[M];
12
13 bool cmp(int a,int b){return a>b;}
14
15 bool DFS(int k,int nowlen,int start)
16 {
17 if (nowlen==0) return DFS(k-1,len,0);
18 if (k==0) return true;
19 int i;
20 for (i=start;i<n;++i)
21 if (!f[i] && a[i]<=nowlen)
22 {
23 f[i] = true;
24 if (DFS(k,nowlen-a[i],i+1)) return true;
25 f[i] = false;
26 if (nowlen==a[i] || nowlen==len)
27 return false;
28 }
29 return false;
30 }
31
32 int main()
33 {
34 int total,ans,i;
35 while (scanf("%d", &n), n)
36 {
37 total = 0;
38 for (i=0;i<n;++i)
39 {
40 scanf("%d", a+i);
41 total += a[i];
42 }
43 sort(a,a+n,cmp);
44 ans = n+1;
45 while (ans--)
46 {
47 if (total%ans) continue;
48 len = total/ans;
49 memset(f, false, sizeof(f));
50 if (DFS(ans,len,0)) break;
51 }
52 printf("%d\n", total/ans);
53 }
54 return 0;
55 }
http://acm.pku.edu.cn/JudgeOnline/problem?id=1190 生日蛋糕深搜剪枝，难，《算法艺术与信息学竞赛》P.181
上下界剪枝：
1、由层数导致的体积上界、下界
最优性剪枝：
1、面积下界 与 当前最优解比较
2、由体积和当前半径导致的最小表面积 S <= 2*V/R (超强）
POJ 1190
1 //1190_生日蛋糕 ~ alpc02
2 #include <stdio.h>
3 #include <string.h>
4
5 #define INF 12345678
6 #define Max_M 21
7 #define Max_R 101
8 #define Max_H 201
9
10 int bottom;
11 int vmax[Max_R][Max_H], vmin[Max_M], smin[Max_M];
12 int V[Max_R][Max_H], S[Max_R][Max_H];
13 int ans = INF;
14
15 void init ()
16 {
17 int i,j;
18
19 for (i=1; i<Max_R; i++)
20 {
21 for (j=1; j<Max_H; j++)
22 {
23 V[i][j] = i*i*j;
24 S[i][j] = 2*i*j;
25 }
26 }
27
28 vmin[0] = smin[0] = 0;
29 for (i=1; i<Max_M; i++)
30 {
31 vmin[i] = vmin[i-1] + V[i][i];
32 smin[i] = smin[i-1] + S[i][i];
33 }
34
35 for (i=0; i<Max_H; i++)
36 vmax[0][i] = 0;
37 for (i=0; i<Max_R; i++)
38 vmax[i][0] = 0;
39
40 for (i=1; i<Max_R; i++)
41 for (j=1; j<Max_H; j++)
42 vmax[i][j] = vmax[i-1][j-1] + V[i][j];
43 }
44
45 void search (int v, int s, int r, int h, int m)
46 {
47 if (m == 0)
48 {
49 if (v == 0)
50 ans = s;
51 return ;
52 }
53
54 int rr, hh;
55 int tv, ts;
56 rr = m;
57 while (s + 2*v/rr >= ans)
58 rr++;
59 for (; rr<=r; rr++)
60 {
61 hh=m;
62 while (vmax[rr][hh] - vmax[rr-m][hh-m] < v) //最大体积 < 当前体积
63 hh++;
64 for (; hh<=h; hh++)
65 {
66 tv = v - V[rr][hh];
67 ts = s + S[rr][hh];
68 if (m == bottom)
69 ts += rr * rr;
70 if (vmin[m-1] > tv) //最小体积 > 剩余体积
71 break;
72 if (ts + smin[m-1] >= ans) //最小面积 >= 当前最优解
73 break;
74 search (tv, ts, rr-1, hh-1, m-1);
75 }
76 if (hh==m)
77 break;
78 }
79 }
80 int main()
81 {
82 init ();
83 int v,m;
84 scanf ("%d", &v);
85 scanf ("%d", &m);
86 bottom = m;
87 search (v, 0, Max_R, Max_H, m);
88 if (ans == INF)
89 ans = 0;
90 printf ("%d\n", ans);
91 return 0;
92 }
http://acm.pku.edu.cn/JudgeOnline/problem?id=1324 Holedox Moving
广搜，A*搜会快一些，中等难度
关键点在于怎么判重、怎么存储蛇：蛇头 + 后面每个点相对于前一点的方向（即0、1、2、3四元值），因此状态空间 20*20*4^(8-1) = 6553600，因此可以用数组判重。
POJ 1324
1 //1324_HoledoxMoving ~ alpc02
2 #pragma warning (disable :4786)
3 #include <stdio.h>
4 #include <map>
5 #include <queue>
6 #include <algorithm>
7 using namespace std;
8
9 const int M = 6553600;
10 const int N = 20;
11 const int L = 8;
12
13 int m,n,l;
14 bool p[N][N];
15 int y[L], x[L];
16
17 struct forQ
18 {
19 int s;
20 int g,h;
21 };
22 bool operator < (const forQ &a, const forQ &b)
23 {
24 return (a.g + a.h) > (b.g + b.h);
25 }
26
27 bool input ()
28 {
29 scanf ("%d %d %d", &m, &n, &l);
30 if (m==0 && n==0 && l==0) return false;
31
32 memset (p, true, sizeof (p));
33 int i, k, ty, tx;
34 for (i=0; i<l; i++)
35 {
36 scanf ("%d %d", y+i, x+i);
37 y[i]--;
38 x[i]--;
39 }
40 scanf ("%d", &k);
41 while (k--)
42 {
43 scanf ("%d %d", &ty, &tx);
44 p[ty-1][tx-1] = false;
45 }
46 return true;
47 }
48
49 priority_queue <forQ> myq;
50 int min_step[M];
51
52 int ty[] = {1,0,0,-1};
53 int tx[] = {0,1,-1,0};
54
55 void init ()
56 {
57 memset (min_step, -1, sizeof(min_step[0]) * 400 * (1<<(2*(l-1))) );
58 while (!myq.empty ())
59 myq.pop ();
60 }
61 void In (int &s, int *y, int *x)
62 {
63 s = 0;
64 int i, j;
65 for (i=l-1; i>=1; i--)
66 {
67 for (j=0; ; j++)
68 if (y[i-1] + ty[j] == y[i] && x[i-1] + tx[j] == x[i])
69 break;
70 s = s * 4 + j;
71 }
72 s = s*20 + y[0];
73 s = s*20 + x[0];
74 }
75 void Out (int s, int *y, int *x)
76 {
77 int i, j;
78
79 x[0] = s % 20;
80 s /= 20;
81 y[0] = s % 20;
82 s /= 20;
83 for (i=1; i<l; i++)
84 {
85 j = s % 4;
86 s = s / 4;
87 y[i] = y[i-1] + ty[j];
88 x[i] = x[i-1] + tx[j];
89 }
90 }
91 struct type
92 {
93 int y,x;
94 type () {}
95 type (int yy,int xx): y(yy), x(xx) {}
96 };
97 bool reachable (int y,int x)
98 {
99 if (y == 0 && x == 0)
100 return true;
101 bool f[N][N];
102 memset (f, false, sizeof(f));
103 queue <type> q;
104 type now;
105 int yy,xx,t;
106
107 q.push (type(y,x));
108 f[y][x] = true;
109
110 while (!q.empty ())
111 {
112 now = q.front ();
113 q.pop ();
114 for (t=0; t<4; t++)
115 {
116 yy = now.y + ty[t];
117 xx = now.x + tx[t];
118 if (yy >= 0 && yy < m && xx >= 0 && xx < n && !f[yy][xx] && p[yy][xx])
119 {
120 if (yy == 0 && xx == 0)
121 return true;
122 f[yy][xx] = true;
123 q.push (type(yy,xx));
124 }
125 }
126 }
127 return false;
128 }
129 int solve ()
130 {
131 if (!reachable (y[0],x[0]))
132 return -1;
133 init ();
134
135 int y1[8],x1[8];
136 int y2[8],x2[8];
137
138 int s;
139 forQ now;
140
141 In (now.s, y, x);
142 now.g = 0;
143 now.h = y[0] + x[0];
144
145 myq.push (now);
146 min_step[now.s] = 0;
147
148 int yy,xx,t,i;
149
150 while (!myq.empty())
151 {
152 now = myq.top ();
153 myq.pop ();
154 if (min_step[now.s] == -2)
155 continue;
156 min_step[now.s] = -2;
157
158 s = now.s;
159 Out (s, y1, x1);
160 if (y1[0] == 0 && x1[0] == 0)
161 return now.g;
162
163 now.g ++;
164 for (i=0; i<l; i++)
165 p[y1[i]][x1[i]] = false;
166 for (t=0; t<4; t++)
167 {
168 for (i=l-1; i>=1; i--)
169 {
170 y2[i] = y1[i-1];
171 x2[i] = x1[i-1];
172 }
173 yy = y1[0] + ty[t];
174 xx = x1[0] + tx[t];
175 if (yy >= 0 && yy < m && xx >= 0 && xx < n && p[yy][xx])
176 {
177 now.s = (( (s/400 % (1<<(2*(l-2))) ) * 4) + (3-t) ) * 400 + yy * 20 + xx;
178 if (min_step[now.s] == -1 || min_step[now.s] > now.g)
179 {
180 now.h = yy + xx;
181 min_step[now.s] = now.g;
182 myq.push (now);
183 }
184 }
185 }
186 for (i=0; i<l; i++)
187 p[y1[i]][x1[i]] = true;
188 }
189 return -1;
190 }
191
192 int main()
193 {
194 int Ca = 0;
195 while (input ())
196 {
197 printf ("Case %d: %d\n", ++Ca, solve ());
198 }
199 return 0;
200 }
http://acm.pku.edu.cn/JudgeOnline/problem?id=2044Weather Forecast用深搜做的，搜到一个解即可退出，中等难度
像上个题一样，关键点还是在于怎么判重、怎么存储状态（当前天是第几天 以及 前6天的天气状况）：最后1天云的位置（0、1、2……8） + 云的变化方向(0、1、2、3、4），状态空间5^5 * 9 * 365 = 10265625，开数组还是非常不错的。
POJ 2044
1 //2044_WeatherForecast ~ alpc02
2 #pragma warning (disable:4786)
3 #include <stdio.h>
4 #include <queue>
5 #include <algorithm>
6 using namespace std;
7
8 const int D = 365;
9 const int N = 9;
10 const int M = 5*5*5*5*5*9*D;
11
12 bool flag[M];
13
14 int rain[N][4] =
15 {
16 {1,2,5,6},
17 {2,3,6,7},
18 {3,4,7,8},
19 {5,6,9,10},
20 {6,7,10,11},
21 {7,8,11,12},
22 {9,10,13,14},
23 {10,11,14,15},
24 {11,12,15,16},
25 };
26 bool israin[N][17];
27
28 bool couldgo[N][N] =
29 {
30 {1,1,1,1,0,0,1,0,0},
31 {1,1,1,0,1,0,0,1,0},
32 {1,1,1,0,0,1,0,0,1},
33 {1,0,0,1,1,1,1,0,0},
34 {0,1,0,1,1,1,0,1,0},
35 {0,0,1,1,1,1,0,0,1},
36 {1,0,0,1,0,0,1,1,1},
37 {0,1,0,0,1,0,1,1,1},
38 {0,0,1,0,0,1,1,1,1},
39 };
40 int go[N][5];
41
42 int d;
43 bool f[D][N];
44
45 void init ()
46 {
47 memset (israin, false, sizeof(israin));
48 int i, j, k;
49 for (i=0; i<N; i++)
50 {
51 for (j=0; j<4; j++)
52 israin[i] [rain[i][j]] = true;
53 }
54 for (i=0; i<N; i++)
55 {
56 k = 0;
57 for (j=0; j<9; j++)
58 if (couldgo[i][j])
59 go[i][k++] = j;
60 }
61 }
62 bool input ()
63 {
64 int sun[17];
65 int i, j, k;
66 scanf ("%d", &d);
67 if (d == 0)
68 return false;
69 for (i=0; i<d; i++)
70 {
71 for (j=1; j<=16; j++)
72 {
73 scanf ("%d", sun+j);
74 }
75 for (j=0; j<9; j++)
76 {
77 for (k=0; k<4; k++)
78 if (sun[rain[j][k]])
79 break;
80 f[i][j] = (k==4);
81 }
82 }
83 return true;
84 }
85
86 struct Go
87 {
88 int j, dif;
89 };
90 bool operator < (const Go &a, const Go &b)
91 {
92 return a.dif < b.dif;
93 }
94
95 int dfs (int s)
96 {
97 if (flag[s])
98 return 0;
99 flag[s] = true;
100 bool six[17] = {0};
101
102 int i, j, k, t, new_s, pre, temp;
103 t = s % d;
104 s /= d;
105
106 if (t == 0)
107 {
108 return 1;
109 }
110
111 int need[12], top=0;
112
113 if (t >= 6)
114 {
115 temp = s;
116 pre = temp % 9;
117 temp /= 9;
118 for (k=0; k<4; k++)
119 six[rain[pre][k]] = true;
120 for (i=0; i<5; i++)
121 {
122 j = go[pre][temp % 5];
123 temp /= 5;
124 for (k=0; k<4; k++)
125 six[rain[j][k]] = true;
126 pre = j;
127 }
128 for (i=1; i<=16; i++)
129 if (!six[i])
130 need[top++] = i;
131 }
132 pre = s % 9;
133 s /= 9;
134 int p, now;
135 Go go_list[9];
136 int go_top = 0;
137 for (j=0; j<9; j++)
138 {
139 if (!f[t][j] || !couldgo[pre][j])
140 continue;
141
142 for (k=0; k<top; k++)
143 if (!israin[j][need[k]])
144 break;
145 if (k == top)
146 {
147 go_list[go_top].j = j;
148 go_list[go_top].dif = 0;
149 now = pre;
150 temp = s;
151 do
152 {
153 if (j != now)
154 ++go_list[go_top].dif;
155 now = go[now] [temp % 5];
156 temp /= 5;
157 }while (temp);
158 go_top++;
159 }
160 }
161 sort (go_list, go_list + go_top);
162 for (i=0; i<go_top; i++)
163 {
164 j = go_list[i].j;
165 for (p=0; p<5; p++)
166 if (go[j][p] == pre)
167 break;
168 new_s = (s % 625) * 5 + p;
169 new_s = new_s * 9 + j;
170 new_s = new_s * d + (t+1) % d;
171 if (dfs (new_s))
172 return 1;
173 }
174 return 0;
175 }
176 int solve ()
177 {
178 if (!f[0][4])
179 return false;
180 memset (flag, false, 5*5*5*5*5*9*d*sizeof(flag[0]));
181 return dfs (4*d+1%d);
182 }
183
184 int main()
185 {
186 init ();
187 while (input ())
188 {
189 printf ("%d\n", solve ());
190 }
191 return 0;
192 }
posted on 2007-08-11 12:27
LSM 阅读(2844)
评论(8) 编辑 收藏 引用 所属分类:
搜索