把最近遇到的搜索好题列一下（推荐做做）。
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