搜索专题(不定期更新)

　　题意：给出一块区域，询问有多少个湖泊？

　　思路：DFS，对于‘W’，深搜一次，并标记已访问。之后每次对未访问的‘W’做一次深搜。

 1 #include<iostream>
 2 #include<memory.h>
 3 using namespace std;
 4 char lake[105][105];
 5 bool vis[105][105];
 6 int n, m;
 7 void DFS(int r, int c)
 8 {
 9     if (r >=n || r<0 || c>=m || c < 0) return;
10     if (lake[r][c] == 'W'&&!vis[r][c])
11     {
12         vis[r][c] = true;
13         DFS(r + 1, c);
14         DFS(r - 1, c);
15         DFS(r, c + 1);
16         DFS(r, c - 1);
17         DFS(r + 1, c + 1);
18         DFS(r + 1, c - 1);
19         DFS(r - 1, c + 1);
20         DFS(r - 1, c - 1);
21     }
22 }
23 int main()
24 {
25     while (cin >> n >> m)
26     {
27         memset(lake, 0, sizeof(lake));
28         memset(vis, 0, sizeof(vis));
29         for (int i = 0; i < n; i++)
30         {
31             for (int j = 0; j < m; j++)
32             {
33                 cin >> lake[i][j];
34             }
35         }
36         int num = 0;
37         for (int i = 0; i < n; i++)
38         {
39             for (int j = 0; j < m; j++)
40             {
41                 if (lake[i][j] == 'W' && !vis[i][j])
42                 {
43                     DFS(i, j);
44                     num++;
45                 }
46             }
47         }
48         cout << num << endl;
49     }
50     return 0;
51 }

POJ 2386 Lake Counting

2、POJ 1979 Red and Black

　　题意：求从‘@’出发，每次只能从4个方向走，且只能走到‘.’的位置，求全部能走到的个数。

　　思路：从‘@’出发DFS一遍即可。

 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 void f(char **p,int x,int y,int x0,int y0,int &sum);
 5 int main()
 6 {
 7     int x, y;
 8     while (cin >> x >> y, x != 0 && y != 0)
 9     {
10         char **p = new char *[y];
11         for (int i = 0; i < y; i++) *(p + i) = new char[x];
12         int x0, y0;
13         for (int i = 0; i < y; i++)
14             for (int j = 0; j < x; j++)
15             {
16                 cin >> p[i][j];
17                 if (p[i][j] == '@')
18                 {
19                     y0 = i;
20                     x0 = j;
21                 }
22             }
23         int sum=0;
24         f(p, x0, y0, x, y, sum);
25         cout << sum << endl;
26         for (int i = 0; i < y; i++) delete[]p[i];
27         delete[]p;
28         p = NULL;
29     }
30     return 0;
31 }
32 void f(char **p, int x, int y, int x0, int y0, int &sum)
33 {
34     if (x >= x0 || x < 0 || y >= y0 || y < 0) return;
35     if (p[y][x] == '#') return;
36     else
37     {
38         sum++;
39         p[y][x] = '#';
40         f(p, x + 1, y, x0, y0, sum);
41         f(p, x - 1, y, x0, y0, sum);
42         f(p, x, y + 1, x0, y0, sum);
43         f(p, x, y - 1, x0, y0, sum);
44     }
45 }

View Code

3、POJ 1321 棋盘问题

　　题意：在一个n*n的矩阵里放k个棋子，只能放在棋盘区域，同时保证每行每列只有最多只有一个棋子。求方案数

　　思路：DFS，按行开始放。

 1 #include<iostream>
 2 using namespace std;
 3 int n, k;
 4 char m[10][10];
 5 int cnt = 0;
 6 bool Judge(int r, int c)
 7 {
 8     for (int i = 0; i < n; i++)
 9     {//判断列是否只有一个
10         if (i == r) continue;
11         if (m[i][c] == '@') return false;
12     }
13     return true;
14 }
15 void DFS(int r, int num)
16 {//按行放
17     if (num == 0)
18     {
19         cnt++;
20         return;
21     }
22     if (r == n)return;
23     for (int i = 0; i < n; i++)
24     {
25         if (m[r][i] == '#')
26         {
27             if (Judge(r, i))
28             {
29                 m[r][i] = '@';
30                 DFS(r + 1, num - 1);
31                 m[r][i] = '#';
32             }
33         }
34     }
35     DFS(r + 1, num);//如果这一行不放棋子
36 }
37 int main()
38 {
39     while (~scanf("%d%d", &n, &k))
40     {
41         if (n == -1 && k == -1)break;
42         for (int i = 0; i < n; i++)
43         {
44             for (int j = 0; j < n; j++) cin >> m[i][j];
45         }
46         cnt = 0;
47         DFS(0, k);
48         printf("%d
", cnt);
49     }
50     return 0;
51 }

View Code

4、POJ 2251 Dungeon Master(BFS)

　　题意：在一个三维空间里，询问能否从起点走到终点，若能，请求出最短时间。

　　思路：BFS，方向为6个。

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstdio>
 4 using namespace std;
 5 char v[35][35][35];//[k][i][j]第k层第i行第j列
 6 struct node
 7 {
 8     int k;
 9     int r;
10     int c;
11     int steps;
12     node(int kk = 0, int rr = 0, int cc = 0,int ss=0):k(kk),r(rr),c(cc),steps(ss){ }
13 };
14 node st, ed;
15 int L, R, C;
16 int dr[] = {1,-1,0,0,0,0};
17 int dc[] = {0,0,1,-1,0,0};
18 int dl[] = {0,0,0,0,1,-1};
19 int main()
20 {
21     while (~scanf("%d%d%d",&L,&R,&C))
22     {
23         if (L == 0 && R == 0 && C == 0)break;
24         for (int k = 0; k < L; k++)
25         {
26             for (int i = 0; i < R; i++)
27             {
28                 for (int j = 0; j < C; j++)
29                 {
30                     cin >> v[k][i][j];
31                     if (v[k][i][j] == 'S') st.k = k, st.r = i, st.c = j,st.steps=0;
32                     if (v[k][i][j] == 'E') ed.k = k, ed.r = i, ed.c = j;
33                 }
34             }
35         }
36         //BFS
37         queue<node>q;
38         q.push(st);
39         v[st.k][st.r][st.c] = '#';
40         bool Find = false;
41         while (!q.empty())
42         {
43             node cur = q.front();
44             q.pop();
45             if (cur.k == ed.k&&cur.r == ed.r&&cur.c == ed.c)
46             {
47                 ed.steps = cur.steps;
48                 Find = true;
49                 break;
50             }
51             int stp = cur.steps;
52             for (int i = 0; i < 6; i++)
53             {
54                 int tr = cur.r + dr[i];
55                 int tc = cur.c + dc[i];
56                 int tl = cur.k + dl[i];
57                 if (tr >= 0 && tr < R&&tc >= 0 && tc < C&&tl >= 0 && tl < L&&v[tl][tr][tc] != '#')
58                 {
59                     q.push(node(tl, tr, tc, stp + 1));
60                     v[tl][tr][tc] = '#';
61                 }
62             }
63         }
64         if (Find) printf("Escaped in %d minute(s).
", ed.steps);
65         else printf("Trapped!
");
66     }
67     return 0;
68 }

View Code

5、HDU 2717/POJ 3278 Catch That Cow

　　题意：在一个数轴上，给出人和牛的位置，每次人可以从当前位置p走到p+1或p-1或2*p的位置，问能抓到牛的最少移动次数。

　　思路：BFS，每次选择合法的走法。

 1 #include<iostream>
 2 #include<queue>
 3 #include<memory.h>
 4 using namespace std;
 5 int n, k;
 6 struct node
 7 {
 8     int pos;
 9     int steps;
10     node(int p=0,int stp=0):pos(p),steps(stp){ }
11 };
12 bool vis[200010];
13 int main()
14 {
15     while (~scanf("%d%d", &n, &k))
16     {
17         //BFS();
18         memset(vis, 0, sizeof(vis));
19         queue<node>q;
20         q.push(node(n,0));
21         vis[n] = true;
22         int ans = 0;
23         while (!q.empty())
24         {
25             node t = q.front();
26             q.pop();
27             int pos = t.pos, stps = t.steps;
28             if (pos == k)
29             {
30                 ans = stps;
31                 break;
32             }
33             if (pos < k)
34             {
35                 if(!vis[pos+1])q.push(node(pos + 1, stps + 1)), vis[pos + 1]=true;
36                 if(!vis[pos*2])q.push(node(pos * 2, stps + 1)),vis[pos*2]=true;
37                 if(pos-1>0&&!vis[pos-1])q.push(node(pos - 1, stps + 1)),vis[pos-1]=true;
38             }
39             else
40             {
41                 if(!vis[pos-1])q.push(node(pos - 1, stps + 1)),vis[pos-1]=true;
42             }
43         }
44         printf("%d
", ans);
45     }
46 
47     return 0;
48 }

View Code

6、POJ 3279 Fliptile

　　题意：给出一个M*N的矩阵，元素为1或0，每次能够选择一个点反转，同时将其上下左右的点都反转(如果点存在的话)，问能使最终矩阵只剩下0时且反转次数最少时的选择反转的点（用矩阵给出）

　　思路：如果第一行我们要反转的点已经确定，那么第一行的0和1的状态就确定，那么第二行的反转的点就会确定，因为此时只有反转第二行的点才能对第一行的1产生影响。走到最后一行，如果在反转最后一行后最后一行都为0，那么我们可以确定这是一种方案。我们枚举第一行选择反转的点的状态，就能知道最后满足题意的反转的方案。

 1 //最多15位，用2进制状态压缩。枚举第一层的反转情况。第一层确定，后面反转状态的都会确定下来
 2 #include<iostream>
 3 using namespace std;
 4 const int maxn = 16;
 5 const int maxp = 16 * 16;
 6 int init[maxn];//存初始状态
 7 int flipstate[maxn];//存反转状态
 8 int state[maxn];//存中间的状态
 9 int ans[maxn],steps;//存结果
10 int n, m;
11 void DFS(int r, int cnt)
12 {
13     if (r == n)
14     {
15         if (state[n - 1] == 0)
16         {
17             if (cnt < steps)
18             {
19                 for (int i = 0; i < n; i++) ans[i] = flipstate[i];
20                 steps = cnt;
21             }//由于我们按照第一行反转状态从小到大DFS，所以如果相等，肯定前面已经保存的字典序小，所以不用再进行判断及赋值操作
22         }
23         return;
24     }
25     flipstate[r] = 0;
26 
27     for (int i = m-1; i>=0; --i)
28     {//从左往右遍历
29         if (state[r - 1] & (1 << i))//前一行为1
30         {
31             flipstate[r] |= 1 << i;//该行灯反转
32             state[r - 1] ^= (1 << i);//保存反转后对格子的影响
33             state[r] ^= (1 << i);
34             if (i + 1 <= m - 1) state[r] ^= (1 << (i + 1));
35             if(i-1>=0) state[r] ^= (1 << (i - 1));
36             if (r + 1 < n) state[r + 1] ^= (1 << i);
37             cnt++;//反转次数累加
38         }
39     }
40     DFS(r + 1, cnt);
41 }
42 void Solve()
43 {
44     int total = (1 << m) - 1;
45     steps = maxp;
46     for (int st = 0; st <= total; st++)
47     {
48         flipstate[0] = st;
49         memcpy(state, init, sizeof(init));
50         int cnt = 0;
51         for (int i = m - 1; i >= 0; --i)
52         {
53             if (st&(1 << i))
54             {
55                 state[0] ^= (1 << i);
56                 if (i + 1 <= m - 1)state[0] ^= (1 << (i + 1));
57                 if (i - 1 >= 0) state[0] ^= (1 << (i - 1));
58                 state[1] ^= (1 << i);
59                 cnt++;
60             }
61         }
62         DFS(1, cnt);
63     }
64 }
65 int main()
66 {
67     while (~scanf("%d%d", &n, &m))
68     {
69         memset(init, 0, sizeof(init));
70         for (int i = 0; i < n; i++)
71         {
72             for (int j = m - 1; j >= 0; --j)
73             {
74                 int num;
75                 scanf("%d", &num);
76                 if (num == 1) init[i] |= (1 << j);
77             }
78         }
79         Solve();
80         if (steps == maxp) printf("IMPOSSIBLE
");
81         else
82         {
83             for (int i = 0; i < n; i++)
84             {
85                 for (int j = m - 1; j >= 0; --j)
86                 {
87                     if (j < m - 1) printf(" ");
88                     if (ans[i] & (1 << j))printf("1");
89                     else printf("0");
90                 }
91                 printf("
");
92             }
93         }
94     }
95     return 0;
96 }

View Code

7、POJ 1426 Find The Multiple

　　题意：对于给定的数n,找到一个数是其倍数，同时该数中只含有1或0.

　　思路：DFS，从1开始枚举，若不是n的倍数，则*10或*10+1,当枚举的数位数超过19位后，直接舍弃。题目能够保证在long long的范围里有解。

 1 //对于n，找到一个只包含数字1和0的数，使它为n的倍数
 2 #include<iostream>
 3 #include<queue>
 4 using namespace std;
 5 long long ans,n;
 6 bool flag = false;
 7 void DFS(long long t,int k)
 8 {
 9     if (flag||k>19) return;
10     if (t%n == 0)
11     {
12         flag = true;
13         ans = t;
14         return;
15     }
16     DFS(t * 10,k+1);
17     if (flag) return;
18     DFS(t * 10 + 1,k+1);
19 }
20 int main()
21 {
22     while(~scanf("%d",&n))
23     {
24         if (n == 0) break;
25         flag = false;
26         DFS(1,1);
27         printf("%lld
",ans);
28     }
29 
30 
31     return 0;
32 }

View Code

8、POJ 3126 Prime Path(素数变换路径)

　　题意：给出一个4位素数，在给出一个要求的素数，问通过最少的变换次数(每次只能把当前素数的某一位换成其他数字，同时变换后的数字要求是素数)从初始的素数变换到要求的素数。

　　思路：先打表判断某一个数是否为素数；然后对于当前一个素数，对其所有位都进行模拟变换，注意最高位不能变换为0，BFS。

 1 #include<iostream>
 2 #include<queue>
 3 using namespace std;
 4 const int maxn = 10005;
 5 bool isp[maxn];
 6 int prime[maxn], cnt;
 7 int ans;
 8 void makePrime()
 9 {
10     memset(isp, true, sizeof(isp));
11     isp[0] = isp[1] = false;
12     cnt = 0;
13     for (int i = 2; i < maxn; ++i)
14     {
15         if (isp[i])//是素数
16         {
17             prime[cnt++] = i;//保存该素数
18         }
19         for (int j = 0; j < cnt && i * prime[j] < maxn; ++j)
20         {
21             isp[i * prime[j]] = false;//当前的数乘以所有已算出的素数都不是素数
22             if (i % prime[j] == 0)//如果i能被某一个最小的素数整除，则退出
23             {
24                 break;
25             }
26         }
27     }
28 }
29 int a, b;
30 int vis[maxn];
31 
32 void BFS()
33 {
34     queue<int>q;
35     q.push(a);
36     vis[a] = 1;
37     while (!q.empty())
38     {
39         int v = q.front();
40         q.pop();
41         //printf("%d %d
", v, vis[v]);
42         if (v == b)
43         {
44             ans = vis[v]-1;
45             return;
46         }
47         int base1 = 10,base2=1;
48         for (int i = 0; i < 4; i++)
49         {
50             for (int j = 0; j <= 9; j++)
51             {
52                 if (v%base1 / base2 == j)continue;
53                 if (i == 3 && j == 0)continue;
54                 int tmp = v / base1*base1 + v%base2 + j*base2;
55                 if (isp[tmp]&&!vis[tmp])
56                 {
57                     vis[tmp] = vis[v]+1;
58                     q.push(tmp);
59                     
60                 }
61             }
62             base1 *= 10;
63             base2 *= 10;
64         }
65     }
66     
67 }
68 int main()
69 {
70     makePrime();
71     int t;
72     scanf("%d", &t);
73     while (t--)
74     {
75         scanf("%d%d", &a, &b);
76         memset(vis, 0, sizeof(vis));
77         BFS();
78         printf("%d
", ans);
79     }
80     return 0;
81 }

View Code

9、POJ 3087 Shuffle'm Up

　　题意：初始有两堆扑克，问能否通过变换得到指定的一堆扑克，若能，求最少次数。

　　思路：BFS，如果变换后再拆分后的结果某次等于初始状态，说明无法变换到指定的堆。否则，不断进行模拟变换和拆分。

 1 #include<iostream>
 2 #include<memory.h>
 3 using namespace std;
 4 char s1[105];
 5 char s2[105];
 6 char des[210];
 7 int main()
 8 {
 9     int t;
10     int Case = 1;
11     scanf("%d", &t);
12     while (t--)
13     {
14         int c;
15         scanf("%d", &c);
16         scanf("%s", s1);
17         scanf("%s", s2);
18         scanf("%s", des);
19         int cnt = 0;
20         char t1[105], t2[105],ts[210];
21         memcpy(t1, s1, sizeof(s1));
22         memcpy(t2, s2, sizeof(s2));
23         while (1)
24         {
25             int len = 0;
26             for (int i = 0; i < c; i++)
27             {
28                 ts[len] = t2[i];
29                 len++;
30                 ts[len] = t1[i];
31                 len++;
32             }
33             cnt++;
34             ts[len] = '';
35             if (strcmp(ts,des)==0)
36             {
37                 break;
38             }
39             for (int i = 0; i < c; i++) t1[i] = ts[i];
40             for (int i = c; i < 2 * c; i++) t2[i-c] = ts[i];
41             if (strcmp(t1,s1)==0 && strcmp(t2,s2)==0)
42             {
43                 cnt = -1;
44                 break;
45             }
46         }
47         printf("%d %d
", Case, cnt);
48         Case++;
49     }
50 
51 
52     return 0;
53 }

View Code

10、poj 3414 Pots (bfs+路径记录)

　　题意：初始有两个空杯，每次可以选择装满一个杯子、倒空一个杯子、从一个杯子倒水到另一个杯子（直到倒水的杯子为空或被倒水的杯子已经被倒满），问能否使最后某个杯子中有C体积的水，能的话求出最少次数，并输出步骤顺序。

　　思路：BFS，用数组来模拟队列（因为需要保存步骤），同时记录杯子水的状态，没有出现过则加入“队列”。如果最后“队列”为“空”（当前指针和长度相等），则说明无法达到题目要求的状态。

 1 #include<iostream>
 2 #include<queue>
 3 #include<memory.h>
 4 #include<cstdio>
 5 using namespace std;
 6 int A, B, C;
 7 struct opt
 8 {
 9     int a;
10     int b;
11     char op;
12     char from;
13     char to;
14     int pre;
15     int cnt;
16     opt(int aa=0,int bb=0,char opp='f',char fr='0',char too='1',int pr=0,int ct=0):a(aa),b(bb),op(opp),from(fr),to(too),pre(pr),cnt(ct){ }
17 };
18 bool vis[110][110];
19 opt ed;
20 opt q[1000005];
21 void Print(int id)
22 {
23     if (id != 0)
24     {
25         Print(q[id].pre);
26         switch (q[id].op)
27         {
28         case 'd':printf("DROP(%c)
", q[id].from);
29             break;
30         case 'f':printf("FILL(%c)
", q[id].from);
31             break;
32         case 'p':printf("POUR(%c,%c)
", q[id].from, q[id].to);
33         }
34     }
35 }
36 int main()
37 {
38     while (~scanf("%d%d%d", &A, &B, &C))
39     {
40         memset(vis, 0, sizeof(vis));
41         memset(q, 0, sizeof(q));
42         vis[0][0] = true;
43         int first = 0;
44         int len = 1;
45         bool flag = false;
46         while (first<len)
47         {
48             opt t = q[first];
49             first++;
50             if (t.a == C || t.b == C)
51             {
52                 flag = true;
53                 ed = t;
54                 break;
55             }
56             if (t.a == 0 && t.b == 0)
57             {
58                 if(!vis[A][0])q[len++]=opt(A, 0,'f','1','1',first-1,t.cnt+1),vis[A][0]=true;
59                 if(!vis[0][B])q[len++]=opt(0, B, 'f', '2','2', first - 1, t.cnt + 1),vis[0][B]=true;
60             }
61             else if(t.a==0)
62             {
63                 int ta = min(A,t.b), tb = (min(A, t.b) == A ? t.b - A : 0);
64                 if(!vis[ta][tb])q[len++]=opt(ta,tb, 'p', '2', '1', first - 1, t.cnt + 1),vis[ta][tb]=true;
65                 if(!vis[A][t.b])q[len++]=opt(A, t.b, 'f', '1', '1', first - 1, t.cnt + 1),vis[A][t.b]=true;
66                 if(!vis[0][B])q[len++]=opt(0, B, 'f', '2', '2', first - 1, t.cnt + 1),vis[0][B]=true;
67             }
68             else if (t.b == 0)
69             {
70                 int ta = (min(t.a, B) == t.a ? 0 : t.a - B),tb= min(t.a, B);
71                 if(!vis[ta][tb])q[len++]=opt(ta,tb, 'p', '1', '2', first - 1, t.cnt + 1),vis[ta][tb]=true;
72                 if (!vis[t.a][B])q[len++]=opt(t.a,B, 'f', '2', '2', first - 1, t.cnt + 1), vis[t.a][B] = true;
73                 if (!vis[A][0])q[len++]=opt(A, 0, 'f', '1', '1', first - 1, t.cnt + 1), vis[A][0] = true;
74             }
75             else
76             {
77                 if (!vis[t.a][0])q[len++]=opt(t.a, 0, 'd', '2', '2', first - 1, t.cnt + 1), vis[t.a][0] = true;
78                 if (!vis[0][t.b])q[len++]=opt(0, t.b, 'd', '1', '1', first - 1, t.cnt + 1), vis[0][t.b] = true;
79                 if (!vis[t.a][B])q[len++] = opt(t.a, B, 'f', '2', '2', first - 1, t.cnt + 1), vis[t.a][B] = true;
80                 if (!vis[A][t.b]) q[len++] = opt(A, t.b, 'f', '1', '1', first - 1, t.cnt + 1), vis[A][t.b] = true;
81                 int ta=(t.b-(A-t.a)>=0?A:t.a+t.b), tb=(t.b-(A-t.a)>=0?t.b-(A-t.a):0);
82                 if (!vis[ta][tb])q[len++] = opt(ta, tb, 'p', '2', '1', first - 1, t.cnt + 1), vis[ta][tb] = true;
83                 ta = (t.a - (B - t.b) >= 0 ? t.a - (B - t.b) : 0), tb = (t.a - (B - t.b) >= 0 ? B : t.b + t.a);
84                 if (!vis[ta][tb])q[len++] = opt(ta, tb, 'p', '1', '2', first - 1, t.cnt + 1), vis[ta][tb] = true;
85             }
86         }
87         if (flag)
88         {
89             printf("%d
", ed.cnt);
90             Print(first - 1);
91         }
92         else printf("impossible
");
93     }
94     return 0;
95 }

View Code

11、UVA11624 Fire!

　　题意：有一个迷宫，有一个人，同时又若干处着火，问能否在火烧到自己之前逃出迷宫，即走到边界，能的话求最少的时间。

　　思路：首先对火进行BFS，初始将所有着火点都放入队列，求出火蔓延到每一处可达的地方的时间；然后对人进行BFS，若某一处可以到达、且没走过、且走到时的时间小于火势蔓延到该处的时间，则加入队列。

  1 #include<iostream>
  2 #include<memory.h>
  3 #include<queue>
  4 using namespace std;
  5 const int INF = 0x7fffffff;
  6 const int maxn = 1005;
  7 int firetime[maxn][maxn];
  8 char mp[maxn][maxn];
  9 int xj, yj;
 10 int n, m;
 11 int dx[] = { 0,0,1,-1 };
 12 int dy[] = { 1,-1,0,0 };
 13 struct point
 14 {
 15     int r;
 16     int c;
 17     int t;
 18     point(int rr=0,int cc=0,int tt=0):r(rr),c(cc),t(tt){ }
 19 };
 20 bool vis[maxn][maxn];
 21 void BFSf()
 22 {
 23     queue<point>q;
 24     for (int i = 0; i < n; i++)
 25     {
 26         for (int j = 0; j < m; j++)
 27         {
 28             if (mp[i][j] == 'F') q.push(point(i, j, 0)),vis[i][j]=true;
 29         }
 30     }
 31     while (!q.empty())
 32     {
 33         point t = q.front();
 34         q.pop();
 35         firetime[t.r][t.c] = t.t;
 36         for (int i = 0; i < 4; i++)
 37         {
 38             int dr = t.r + dx[i];
 39             int dc = t.c + dy[i];
 40             if (dr < n&&dr >= 0 && dc < m&&dc >= 0)
 41             {
 42                 if (mp[dr][dc] != '#'&&!vis[dr][dc])
 43                 {
 44                     vis[dr][dc] = true;
 45                     q.push(point(dr, dc, t.t + 1));
 46                 }
 47             }
 48         }
 49     }
 50 }
 51 int ans = INF;
 52 
 53 void BFSj()
 54 {
 55     queue<point>q;
 56     q.push(point(xj, yj, 0));
 57     vis[xj][yj] = true;
 58     while (!q.empty())
 59     {
 60         point t = q.front();
 61         q.pop();
 62         if (t.r == n - 1 || t.r == 0 || t.c == m - 1 || t.c == 0)
 63         {
 64             ans = t.t;
 65             return;
 66         }
 67         for (int i = 0; i < 4; i++)
 68         {
 69             int dr = t.r + dx[i];
 70             int dc = t.c + dy[i];
 71             if (dr <= n - 1 && dr >= 0 && dc <= m - 1 && dc >= 0)
 72             {
 73                 if (mp[dr][dc] != '#' && !vis[dr][dc] && t.t + 1 < firetime[dr][dc])
 74                 {
 75                     vis[dr][dc] = true;
 76                     q.push(point(dr, dc, t.t + 1));
 77                 }
 78             }
 79         }
 80     }
 81     ans = INF;
 82 }
 83 int main()
 84 {
 85     //std::ios::sync_with_stdio(false);
 86     int t;
 87     scanf("%d", &t);
 88     while (t--)
 89     {
 90         scanf("%d%d", &n, &m);
 91         for (int i = 0; i < n; i++)
 92         {
 93             for (int j = 0; j < m; j++)
 94             {
 95                 cin >> mp[i][j];
 96                 if (mp[i][j] == 'J') xj = i, yj = j;
 97                 firetime[i][j] = INF;
 98             }
 99         }
100         memset(vis, 0, sizeof(vis));
101         BFSf();
102         memset(vis, 0, sizeof(vis));
103         ans = INF;
104         BFSj();
105         if (ans == INF)
106         {
107             printf("IMPOSSIBLE
");
108         }
109         else
110         {
111             printf("%d
", ans+1);
112         }
113     }
114     return 0;
115 }

View Code

12、HDU1241 Oil Deposits

　　题意：给出一个地图，上面标记有油的地方，问有多少个油田（上下左右、左上左下右上右下如果和该处都有油，则属于同一个油田）

　　思路：简单DFS。

 1 #include<iostream>
 2 #include<memory.h>
 3 using namespace std;
 4 char mp[110][110];
 5 int n, m;
 6 bool vis[110][110];
 7 int dr[] = {0,-1,-1,-1,0,1,1,1};
 8 int dc[] = {-1,-1,0,1,1,1,0,-1};
 9 void DFS(int r, int c)
10 {
11     vis[r][c] = true;
12     for (int i = 0; i < 8; i++)
13     {
14         int tr = r + dr[i];
15         int tc = c + dc[i];
16         if (tr < n&&tr >= 0 && tc < m&&tc >= 0)
17         {
18             if (mp[tr][tc] == '@' && !vis[tr][tc])
19                 DFS(tr, tc);
20         }
21     }
22 }
23 int main()
24 {
25     while (~scanf("%d%d", &n, &m))
26     {
27         if (m == 0) break;
28         for (int i = 0; i < n; i++)
29         {
30             for (int j = 0; j < m; j++) cin >> mp[i][j];
31         }
32         memset(vis, 0, sizeof(vis));
33         int cnt = 0;
34         for (int i = 0; i < n; i++)
35         {
36             for (int j = 0; j < m; j++)
37             {
38                 if (mp[i][j] == '@' && !vis[i][j])
39                 {
40                     DFS(i, j);
41                     cnt++;
42                 }
43             }
44         }
45         printf("%d
", cnt);
46     }
47 
48     return 0;
49 }

View Code

13、HDU 1495 非常可乐(广搜BFS)

　　题意：有一瓶满的可乐，还有两个杯子。每次可以从一个容器倒到另一个容器（直到一个为空或一个为满），问能否使该瓶可乐平分。

　　思路：BFS。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<memory.h>
 5 using namespace std;
 6 int S, N, M;
 7 struct node
 8 {
 9     int s;
10     int n;
11     int m;
12     int step;
13     node(int ss=0,int nn=0,int mm=0,int st=0):s(ss),n(nn),m(mm),step(st){ }
14 };
15 bool vis[110][110][110];
16 int main()
17 {
18     while (~scanf("%d%d%d", &S, &N, &M))
19     {
20         if (S == 0 && N == 0 && M == 0) break;
21         if (S % 2 == 1)
22         {
23             printf("NO
");
24             continue;
25         }
26         memset(vis, 0, sizeof(vis));
27         queue<node>q;
28         q.push(node(S, 0, 0, 0));
29         vis[S][0][0] = true;
30         bool flag = false;
31         int ans;
32         while (!q.empty())
33         {
34             node t = q.front();
35             q.pop();
36             if ((t.s == S / 2 && t.n == S / 2) || (t.s == S / 2 && t.m == S / 2) || (t.n == S / 2 && t.m == S / 2))
37             {
38                 flag = true;
39                 ans = t.step;
40                 break;
41             }
42             if (t.s)
43             {
44                 int ts = (t.s - (N - t.n) >= 0 ? t.s - (N - t.n) : 0);
45                 int tn = (t.s - (N - t.n) >= 0 ? N : t.s + t.n);
46                 if (!vis[ts][tn][t.m]) q.push(node(ts, tn, t.m, t.step + 1)),vis[ts][tn][t.m]=true;
47                 ts = (t.s - (M - t.m) >= 0 ? t.s - (M - t.m) : 0);
48                 int tm = (t.s - (M - t.m) >= 0 ? M : t.s + t.m);
49                 if (!vis[ts][t.n][tm]) q.push(node(ts, t.n, tm, t.step + 1)), vis[ts][t.n][tm] = true;
50             }
51             if (t.n)
52             {
53                 int tn = 0, ts = t.s + t.n;
54                 if (!vis[ts][tn][t.m]) q.push(node(ts, tn, t.m, t.step + 1)), vis[ts][tn][t.m] = true;
55                 tn = (t.n - (M - t.m) >= 0 ? t.n - (M - t.m) : 0);
56                 int tm = (t.n - (M - t.m) >= 0 ? M : t.n + t.m);
57                 if (!vis[t.s][tn][tm])q.push(node(t.s, tn, tm, t.step + 1)), vis[t.s][tn][tm] = true;
58             }
59             if (t.m)
60             {
61                 int tm = 0, ts = t.s + t.m;
62                 if (!vis[ts][t.n][tm])q.push(node(ts, t.n, tm, t.step + 1)), vis[ts][t.n][tm] = true;
63                 tm = (t.m - (N - t.n) >= 0 ? t.m - (N - t.n) : 0);
64                 int tn = (t.m - (N - t.n) >= 0 ? N : t.m + t.n);
65                 if (!vis[t.s][tn][tm])q.push(node(t.s, tn, tm, t.step + 1)), vis[t.s][tn][tm] = true;
66             }
67         }
68         if (flag)printf("%d
", ans);
69         else printf("NO
");
70     }
71 
72 
73     return 0;
74 }

View Code

14、hdu 2612 Find a way (BFS)

　　题意：有两个人，有几家KFC店，现在这两个人商量到某一家KFC。求两个人到KFC店的最少的用时，每次走一步花费11分钟。

　　思路：对两个人分别BFS，求出其到各家KFC店的最短用时。

 1 #include<iostream>
 2 #include<map>
 3 #include<queue>
 4 #include<memory.h>
 5 using namespace std;
 6 char mp[210][210];
 7 map<pair<int, int>, int>kfc;
 8 bool vis[210][210];
 9 const int maxt = 0x7fffffff;
10 struct node
11 {
12     int r;
13     int c;
14     int tm;
15     node(int rr=0,int cc=0,int tt=0):r(rr),c(cc),tm(tt){ }
16 };
17 int Yx, Yy, Mx, My;
18 int n, m;
19 int dx[] = { 0,0,1,-1 };
20 int dy[] = { 1,-1,0,0 };
21 int ans,cntkfc;
22 void BFS(int inir,int inic)
23 {
24     memset(vis, 0, sizeof(vis));
25     cntkfc = kfc.size();
26     queue<node>q;
27     q.push(node(inir,inic, 0));
28     vis[inir][inic] = true;
29     pair<int, int>p;
30     while (!q.empty())
31     {
32         node t = q.front();
33         p.first = t.r, p.second = t.c;
34         q.pop();
35         if (kfc[p])
36         {
37             cntkfc--;
38             if (kfc[p] > 11) ans = min(ans, kfc[p] + t.tm - 11);
39             kfc[p] += t.tm;
40             if (cntkfc == 0)return;
41         }
42         for (int i = 0; i < 4; i++)
43         {
44             int tr = t.r + dx[i];
45             int tc = t.c + dy[i];
46             if (tr >= 0 && tr < n&&tc >= 0 && tc < m)
47             {
48                 if (mp[tr][tc] != '#' && !vis[tr][tc])
49                 {
50                     vis[tr][tc] = true;
51                     q.push(node(tr, tc, t.tm + 11));
52                 }
53             }
54         }
55     }
56 }
57 int main()
58 {
59     while (~scanf("%d%d", &n, &m))
60     {
61         kfc.clear();
62         for (int i = 0; i < n; i++)
63         {
64             for (int j = 0; j < m; j++)
65             {
66                 cin >> mp[i][j];
67                 if (mp[i][j] == 'Y') Yx = i, Yy = j;
68                 if (mp[i][j] == 'M')Mx = i, My = j;
69                 if (mp[i][j] == '@') kfc[make_pair(i, j)] = 11;
70             }
71         }
72         ans = maxt;
73         BFS(Yx, Yy);
74         BFS(Mx, My);
75         printf("%d
", ans);
76     }
77     return 0;
78 }

View Code

进阶题

1、Eight hdu 1043/POJ 1077（双向广搜+康拓展开）

　　题意：八数码，在一个九宫格里给出1~8的位置，剩下一个为空。求经过最少多少步后能够达到目标状态，并且给出走法（字符串）

　　思路：①双向广搜+康拓展开hash

　　　　　　1、由于每一种状态都是0~8的一个排列，每一个排列对应康拓展开的一个值，建立hash，以便判重

　　　　　　2、双向广搜，此处用两个队列同时进行，用vis分别记录在此队列中某一状态是否出现过。并用数组来记录所有的走法。当两者相遇时，则递归输出路径。

　　　　　　3、由于在八数码中，任意交换两个数字的位置不改变逆序数的奇偶性，所以可以事先判断初始和目标状态的逆序数的奇偶性。

  1 #include<iostream>
  2 #include<string>
  3 #include<cstring>
  4 #include<queue>
  5 #include<algorithm>
  6 using namespace std;
  7 
  8 const int maxn = 400000;
  9 const char* DIR1 = "udlr";//上下左右
 10 const char* DIR2 = "durl";//下上右左，因为从终点开始广搜，然后从中间状态要走到终点，方向反
 11 
 12 int kthash[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320 }; //康拓展开的阶乘值
 13 
 14 int x; //初始状态x的位置
 15 
 16 int dir[] = { -3, 3, -1, 1 };//在数组里的位置变化。向上走位置-3，向下走位置+3，向左走位置-1，向右走位置+1
 17 
 18 int vis1[maxn];//起点广搜标记
 19 int vis2[maxn];//终点广搜标记
 20 
 21 char ss[] = "123456780";//目标即最终状态
 22 char str[10];//初始状态
 23 
 24 struct Node
 25 {
 26     int x;//'x'的位置
 27     char str[10];//棋子的状态
 28 };//用于广搜时队列的元素
 29 
 30 struct Step
 31 {
 32     int cnt;
 33     char dir;
 34 }pre[maxn];//记录路径
 35 int Hush(char* a)  //计算康托展开值
 36 {
 37     int s = 0, i, j, k;
 38     for (i = 0; i<9; i++)
 39     {
 40         k = 0;
 41         for (j = 0; j<i; j++)
 42             if (a[j]>a[i])k++;
 43         s += k*kthash[i];
 44     }
 45     return s;
 46 }
 47 
 48 
 49 void printfff(int x)  //追溯到起点输出路径
 50 {
 51     if (pre[x].cnt == -1)  return;
 52     printfff(pre[x].cnt);
 53     cout << pre[x].dir;
 54 }
 55 
 56 int judge(int x, int i)   //判断是否越界，x为'0'(代表'x')在一维数组的位置
 57 {
 58     int xx = x / 3;  //行
 59     int yy = x % 3;  //列
 60     if (i == 3)//向右走
 61     {
 62         int yyy = yy + 1;
 63         if (yyy > 2)  return 0;
 64     }
 65     if (i == 2)//向左走
 66     {
 67         int yyy = yy - 1;
 68         if (yyy < 0)   return 0;
 69     }
 70     if (i == 1)//向下走
 71     {
 72         int xxx = xx + 1;
 73         if (xxx>2)    return 0;
 74     }
 75     if (i == 0)//向上走
 76     {
 77         int xxx = xx - 1;
 78         if (xxx < 0) return 0;
 79     }
 80     return 1;
 81 }
 82 
 83 void bfs()
 84 {
 85     memset(vis1, 0, sizeof(vis1));//从起点BFS标记数组
 86     memset(vis2, 0, sizeof(vis2));//从终点BFS标记数组
 87 
 88     queue<Node> q1, q2;//q1起点BFS，q2终点BFS
 89     Node p1, p2;
 90 
 91     int count = 2;
 92     strcpy(p1.str, str);  //初始状态
 93     p1.x = x;             //初始x的位置
 94                           //cout << p1.str << endl;
 95     strcpy(p2.str, ss);   //最终状态
 96     p2.x = 8;             //最终x的位置
 97                           //cout << p2.str << endl;
 98     q1.push(p1);
 99     q2.push(p2);
100     vis1[Hush(str)] = 1;//为0表示没有访问，否则表示pre[]访问位置
101     vis2[Hush(ss)] = 2;
102     pre[1].cnt = -1;  //起点标记
103     pre[2].cnt = -1;  //终点标记
104     while (!q1.empty() && !q2.empty())
105     {
106         Node u = q1.front();
107         q1.pop();
108         int p = Hush(u.str);
109         if (vis2[p])  //在终点广搜中出现过
110         {
111             printfff(vis1[p]);//先打印从起点到该点
112             int k = vis2[p];
113             while (pre[k].cnt != -1)//打印从该点到终点
114             {
115                 cout << pre[k].dir;
116                 k = pre[k].cnt;
117             }
118             cout << endl;
119             return;
120         }
121         else //未找到目标状态
122         {
123             Node u2;
124             for (int i = 0; i < 4; i++)
125             {
126                 u2 = u;
127                 if (!judge(u.x, i))  continue;
128                 int xx = u.x + dir[i]; //x的新地址
129                 swap(u2.str[u.x], u2.str[xx]);
130                 u2.x = xx;
131                 int v = Hush(u2.str);
132                 if (vis1[v])  continue; //已访问
133                 vis1[v] = ++count;
134                 pre[count].dir = DIR1[i]; //记录方向
135                 pre[count].cnt = vis1[p];
136                 q1.push(u2);
137             }
138         }
139 
140         u = q2.front();
141         q2.pop();
142         p = Hush(u.str);
143         if (vis1[p])
144         {
145             printfff(vis1[p]);
146             int k = vis2[p];
147             while (pre[k].cnt != -1)
148             {
149                 cout << pre[k].dir;
150                 k = pre[k].cnt;
151             }
152             cout << endl;
153             return;
154         }
155         else //未找到目标状态
156         {
157             Node u2;
158             for (int i = 0; i < 4; i++)
159             {
160                 u2 = u;
161                 if (!judge(u.x, i))  continue;
162                 int xx = u.x + dir[i]; //x的新地址
163                 swap(u2.str[u.x], u2.str[xx]);
164                 u2.x = xx;
165                 int v = Hush(u2.str);
166                 if (vis2[v])  continue; //已访问
167                 vis2[v] = ++count;
168                 pre[count].dir = DIR2[i]; //记录方向
169                 pre[count].cnt = vis2[p];
170                 q2.push(u2);
171             }
172         }
173     }
174     cout << "unsolvable" << endl;
175 }
176 
177 
178 int main()
179 {
180 
181     char s[40];
182     while (gets_s(s,40))
183     {
184         int k = 0;
185         int t = 0;
186         for (int i = 0; s[i] !=''; i++)
187         {
188             if (s[i] == ' ')continue;
189             if (s[i] == 'x')
190             {
191                 str[k] = '0'; 
192                 x = k;
193             }
194             else str[k] = s[i];
195             k++;
196         }
197         str[k] = '';
198 
199         for (int i = 0; i<9; i++)  //逆序数判断是否可行
200         {
201             if (str[i] == '0')continue;
202             for (int j = 0; j<i; j++)
203             {
204                 if (str[j] == '0')continue;
205                 if (str[j]>str[i])t++;
206             }
207         }
208         if (t & 1) cout << "unsolvable" << endl;//逆序数为奇数，则不可行
209         else bfs();
210     }
211     return 0;
212 }

View Code

2、Eight II HDU 3567

　　题意：和上题类似，不过不再是Special Judge,需要给出从初始状态到目标状态的最小移动步数，同时如果在最小步数下有多种走法，给出字典序最小的走法。

　　思路：①双向广搜+康拓展开hash

　　　　　　1、由于需要进行路径的比较，用4进制表示路径来保存。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 #include <iostream>
  7 #include <queue>
  8 #include <map>
  9 #include <vector>
 10 #include<string>
 11 using namespace std;
 12 
 13 #define LL __int64
 14 const int maxn = (int)4e5 + 10;
 15 const int INF = (int)1e8;
 16 int ha[9] = { 1,1,2,6,24,120,720,5040,40320 };//康拓哈希
 17 int dir[4][2] = { { 1,0 },{ 0,-1 },{ 0,1 },{ -1,0 } };//下d 左l 右r 上u
 18 char d[10] = { "dlru" };
 19 LL dd[2][4] = { { 0,1,2,3 },{ 3,2,1,0 } };
 20 int vis[2][maxn], t, Min_ans;//vis记录最短到底目标的时间
 21 char ans[maxn], get[maxn];
 22 LL c[2][maxn];//c[i][j]表示i状态下，j哈希值时的最小路径
 23 LL mm[30];  //mm[i]表示4^i
 24 struct node
 25 {
 26     int f[3][3];//状态
 27     int x, y;//'0'的位置
 28     int g;//表示在格子BFS中的步数
 29     int flag;//0表示前BFS，1表示后BFS
 30     LL path;//4进制表示的路径
 31     int hash_num;//hash值
 32 };
 33 int get_hash(node e)//康托展开，压缩空间。
 34 {
 35     int a[9], i, j, k = 0, ans = 0;
 36     for (i = 0; i<3; i++)
 37     {
 38         for (j = 0; j<3; j++)
 39             a[k++] = e.f[i][j];
 40     }
 41     for (i = 0; i<9; i++)
 42     {
 43         k = 0;
 44         for (j = 0; j<i; j++)
 45             if (a[j]>a[i])k++;
 46         ans += ha[i] * k;
 47     }
 48     return ans;
 49 }
 50 string get_str(LL c, int flag, int kk)//从数字转换成路径
 51 {
 52     int str[100];
 53     int i, k = 0;
 54     for (i = 0; i<vis[flag][kk]; i++)
 55     {
 56         str[k++] = c % 4;
 57         c = c / 4;
 58     }
 59     string s = "";
 60     for (i = k - 1; i >= 0; i--)
 61         s += d[str[i]];
 62     return s;
 63 }
 64 void bfs(node e, node ee)//双向bfs
 65 {
 66     memset(vis, -1, sizeof(vis));
 67     int i, j, k, xx, yy, dis[2];
 68     dis[0] = dis[1] = 0;
 69     node a, b;
 70     e.hash_num = get_hash(e);
 71     e.g = 0, e.flag = 0;
 72     e.path = 0;
 73     ee.hash_num = get_hash(ee);
 74     ee.g = 0, ee.flag = 1;
 75     ee.path = 0;
 76     vis[0][e.hash_num] = 0;
 77     vis[1][ee.hash_num] = 0;
 78     if (e.hash_num == ee.hash_num)
 79     {
 80         printf("0

"); return;
 81     }
 82 
 83     queue<node>q;
 84     q.push(e);//压入起点
 85     q.push(ee);//压入终点
 86     Min_ans = INF;
 87     LL str;
 88     string res;
 89     while (!q.empty())
 90     {
 91         e = q.front();
 92         q.pop();
 93 
 94         for (i = 0; i<4; i++)
 95         {//四个方向
 96             a = e;
 97             a.x = e.x + dir[i][0];
 98             a.y = e.y + dir[i][1];
 99             if (a.x<0 || a.y<0 || a.x >= 3 || a.y >= 3)continue;
100             swap(a.f[e.x][e.y], a.f[a.x][a.y]);
101             k = get_hash(a);
102             if (vis[e.flag][k] != -1)//如果已经访问过
103             {
104                 if (e.g + 1>vis[e.flag][k])continue;
105                 else//如果可以更早到达
106                 {
107                     if (e.flag)str = dd[e.flag][i] * mm[e.g] + e.path;//后DFS
108                     else str = e.path * 4 + dd[e.flag][i];//前DFS
109                     if (c[e.flag][k]>str)
110                         c[e.flag][k] = str;
111                 }
112             }
113             else//没有访问过
114             {
115                 vis[e.flag][k] = e.g + 1;
116                 if (e.flag)c[e.flag][k] = dd[e.flag][i] * mm[e.g] + e.path;
117                 else c[e.flag][k] = e.path * 4 + dd[e.flag][i];
118             }
119             a.hash_num = k;
120             a.g++;
121             a.path = c[e.flag][k];
122             if (vis[e.flag ^ 1][k] != -1)//如果在另一个BFS中出现过
123             {
124                 //cout<<vis[0][k]+vis[1][k]<<endl;
125                 //cout<<c[0][k]<<" "<<c[1][k]<<endl;
126                 string s = get_str(c[0][k], 0, k) + get_str(c[1][k], 1, k);//得到路径
127                 //cout<<s<<endl;
128                 t = s.length();
129                 if (t>Min_ans)
130                 {//如果大于
131                     cout << Min_ans << endl;
132                     cout << res << endl;
133                     return;
134                 }
135                 if (t<Min_ans)
136                 {//如果小于
137                     Min_ans = t;
138                     res = s;
139                 }
140                 else
141                 {
142                     if (res.compare(s)>0)res = s;
143                 }
144             }
145             q.push(a);
146         }
147     }
148 }
149 void init()
150 {//4进制表示路径
151     int i, j, k;
152     mm[0] = 1;
153     for (i = 1; i <= 30; i++)
154         mm[i] = mm[i - 1] * 4;
155 }
156 int main()
157 {
158     init();
159     char a[30], b[30];
160     int T, tt = 0;
161     scanf("%d", &T);
162     while (T--)
163     {
164         int i, j, k, n;
165         node e, pp;
166         scanf("%s", a);
167         scanf("%s", b);
168         n = strlen(a);
169         for (i = 0; i<n; i++)
170         {
171             if (a[i] == 'X')
172             {
173                 e.f[i / 3][i % 3] = 0; e.x = i / 3; e.y = i % 3;
174             }
175             else e.f[i / 3][i % 3] = a[i] - '0';
176             if (b[i] == 'X')
177             {
178                 pp.f[i / 3][i % 3] = 0; pp.x = i / 3; pp.y = i % 3;
179             }
180             else pp.f[i / 3][i % 3] = b[i] - '0';
181         }
182         printf("Case %d: ", ++tt);
183         bfs(e, pp);
184     }
185     return 0;
186 }

View Code

3、HDU2181 哈密顿绕行世界问题(DFS)

　　题意：共有20各城市，给出每个城市相邻的3个城市，求从一个城市m出发，经过所有城市后回到m的所有方案，按字典序输出。

　　思路：每次判断是否走过，从小的城市开始DFS。

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int mp[25][3];
 5 int line[25];
 6 int vis[25];
 7 int Case;
 8 void DFS(int st,int cur, int len)
 9 {
10     if (cur == st&&len == 21)
11     {
12         printf("%d: ", Case);
13         for (int i = 0; i < 21; i++) printf(" %d", line[i]);
14         printf("
");
15         Case++;
16         return;
17     }
18     for (int i = 0; i < 3; i++)
19     {
20         if (!vis[mp[cur][i]]&&(mp[cur][i]!=st||len==20))
21         {
22             line[len] = mp[cur][i];
23             vis[mp[cur][i]] = true;
24             DFS(st, mp[cur][i], len + 1);
25             vis[mp[cur][i]] = false;
26         }
27     }
28 }
29 int main()
30 {
31     int lct[3];
32     for (int i = 1; i <= 20; i++)
33     {
34         for (int j = 0; j < 3; j++) scanf("%d", &mp[i][j]);
35     }
36     int m;
37     memset(vis, 0, sizeof(vis));
38     while (~scanf("%d", &m))
39     {
40         if (m == 0)break;
41         Case = 1;
42         line[0] = m;
43         DFS(m,m, 1);
44     }
45     return 0;
46 }

View Code

4、HDU3533 Escape(BFS)

　　题意：从（0,0）走到(n,m),图中有若干个炮塔，会周期性的对其朝向位置发射一颗子弹，子弹遇到边界或另一个炮塔就会消失。现在需要在给定时间内到达且不能被炮塔打到，每走一步或待在原地时间+1.

　　思路：先预处理在给定的时间内，每个炮塔发出的子弹在何时会到达何处。然后进行BFS。

  1 #include<iostream>
  2 #include<memory.h>
  3 #include<queue>
  4 using namespace std;
  5 int m, n, k, d;//行数，列数，炮塔数，总能量
  6 const int maxn = 105;
  7 const int maxt = 1005;
  8 bool iscan[maxn][maxn][maxt];//第i行第j列第dt时间能不能通过
  9 bool vis[maxn][maxn][maxt];//第i行第j列第dt时间是否曾经走过
 10 struct node
 11 {
 12     int r;
 13     int c;
 14     int t;
 15     node(int rr=0,int cc=0,int tt=0):r(rr),c(cc),t(tt){ }
 16 };
 17 
 18 bool ppos[maxn][maxn];//第i行第j列是否有炮塔
 19 
 20 int dr[] = { 0,0,0,-1,1 };
 21 int dc[] = { 0,1,-1,0,0 };
 22 struct pao
 23 {
 24     int r;
 25     int c;
 26     int v;//子弹速度
 27     int period;//周期
 28     char dir;//朝向'N'上'S'下'W'左'E'右
 29 }Pao[maxn];
 30 void Init()//初始化iscan数组
 31 {
 32     memset(vis, 0, sizeof(vis));
 33     memset(iscan, true, sizeof(iscan));
 34     memset(ppos, 0, sizeof(ppos));
 35     pao temp;
 36     char op[3];
 37     for (int i = 0; i < k; i++)
 38     {
 39         scanf("%s%d%d%d%d", &op, &temp.period, &temp.v, &temp.r, &temp.c);
 40         temp.dir = op[0];
 41         ppos[temp.r][temp.c] = true;
 42         Pao[i] = temp;
 43     }
 44     memset(iscan[0][0], false, sizeof(iscan[0][0]));//敌人大本营肯定不能待
 45     for (int i = 0; i < k; i++)
 46     {//分别对每个炮塔进行初始化
 47         pao p = Pao[i];
 48         memset(iscan[p.r][p.c], false , sizeof(iscan[p.r][p.c]));
 49         bool flag = false;
 50         //先判断在朝向上有无炮塔
 51         int edr = 0, edc=0;
 52         switch (p.dir)//找到子弹能够射的距离
 53         {
 54         case 'N':
 55             edc = p.c;
 56             for (edr = p.r - 1; edr >= 0; edr--) if (ppos[edr][edc])break;
 57             if (edr < 0)edr = 0;
 58             for (int ps = p.r - p.v,init=1; ps >= edr;init++, ps -= p.v)
 59             {//枚举位置
 60                 for (int t = init; t <= d; t += p.period) iscan[ps][p.c][t] = false;
 61             }
 62             break;
 63         case 'S':
 64             edc = p.c;
 65             for (edr = p.r + 1; edr <= m; edr++)if (ppos[edr][edc])break;
 66             if (edr > m) edr = m;
 67             for (int ps = p.r + p.v, init = 1; ps <= edr; init++, ps += p.v)
 68             {//枚举位置
 69                 for (int t = init; t <= d; t += p.period) iscan[ps][p.c][t] = false;
 70             }
 71             break;
 72         case 'W':
 73             edr = p.r;
 74             for (edc = p.c - 1; edc >= 0; edc--)if (ppos[edr][edc])break;
 75             if (edc < 0)edc = 0;
 76             for (int ps = p.c-p.v, init = 1; ps >= edc; init++, ps -= p.v)
 77             {//枚举位置
 78                 for (int t = init; t <= d; t += p.period) iscan[p.r][ps][t] = false;
 79             }
 80             break;
 81         case 'E':
 82             edr = p.r;
 83             for (edc = p.c + 1; edc <=n; edc++)if (ppos[edr][edc])break;
 84             if (edc > n)edc = n;
 85             for (int ps = p.r + p.v, init = 1; ps <= edr; init++, ps += p.v)
 86             {//枚举位置
 87                 for (int t = init; t <= d; t += p.period) iscan[p.r][ps][t] = false;
 88             }
 89             break;
 90         }   
 91     }
 92 }
 93 void BFS()
 94 {
 95     queue<node>q;
 96     q.push(node(0, 0,0));
 97     vis[0][0][0] = true;
 98     while (!q.empty())
 99     {
100         node u = q.front();
101         q.pop();
102         if (u.r == m&&u.c == n)
103         {
104             printf("%d
", u.t);
105             return;
106         }
107         for (int i = 0; i < 5; i++)
108         {
109             int tr = u.r + dr[i];
110             int tc = u.c + dc[i];
111             int tt = u.t + 1;
112             if (tr <= m&&tr >= 0 && tc <= n&&tc >= 0)
113             {//没有超范围
114                 if (!ppos[tr][tc]&&!vis[tr][tc][tt] && iscan[tr][tc][tt]&&tt<=d)
115                 {//没有访问过且能够走
116                     q.push(node(tr, tc, tt));
117                     vis[tr][tc][tt] = true;
118                 }
119             }
120         }
121     }
122     printf("Bad luck!
");
123 }
124 int main()
125 {
126     while (~scanf("%d%d%d%d", &m, &n, &k, &d))
127     {
128         Init();
129         BFS();
130     }
131     return 0;
132 }

View Code

5、DNA sequence HDU 1560

　　题意：给出若干个长度不一定相同的DNA序列，现在需要构造一个最短的序列，使每一个给出的DNA序列都是它的一个子序列（不一定连续）

　　思路：迭代深搜，对于某一个限制的长度，看看能否达到要求。对于某一个位置，看看能否放置某一个字母（如果所有序列剩下的需要匹配的第一个字符有它），有就进行一次DFS。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 char str[10][10];//记录n个字符串
 7 int n, ans, deep, Size[10];
 8 char DNA[4] = { 'A','C','G','T' };//一共四种可能
 9 
10 void dfs(int cnt, int *len)
11 {
12     if (cnt > deep)//大于限制的深度，不用往下搜索
13         return;
14     int maxx = 0;//预计还要匹配的字符串的最大长度
15     for (int i = 0; i<n; i++)
16     {
17         int t = Size[i] - len[i];
18         if (t>maxx)
19             maxx = t;
20     }
21     if (maxx == 0)//条件全部满足即为最优解
22     {
23         ans = cnt;
24         return;
25     }
26     if (cnt + maxx > deep)//剪枝
27         return;
28     for (int i = 0; i<4; i++)
29     {
30         int pos[10];//保存在当前字符被选择为构造的字符串的字符时，剩下的字符串开始需要匹配的位置
31         int flag = 0;//判断是否有字符串的当前要匹配的位置是该字符
32         for (int j = 0; j<n; j++)
33         {//枚举每一个字符串，计算pos值
34             if (str[j][len[j]] == DNA[i])
35             {
36                 flag = 1;
37                 pos[j] = len[j] + 1;
38             }
39             else
40                 pos[j] = len[j];
41         }
42         if (flag)//如果匹配的话
43             dfs(cnt + 1, pos);//继续搜索
44         if (ans != -1)//如果搜索到的话，直接返回
45             break;
46     }
47 }
48 
49 int main()
50 {
51     int t;
52     cin >> t;
53     while (t--)
54     {
55         cin >> n;
56         int minn = 0;
57         for (int i = 0; i<n; i++)
58         {
59             cin >> str[i];
60             Size[i] = strlen(str[i]);//记录长度
61             if (Size[i]>minn)
62                 minn = Size[i];
63         }
64         ans = -1;
65         deep = minn;//从最短长度开始搜索
66         int pos[10] = { 0 };//记录n个字符串目前匹配到的位置
67         while (1)
68         {
69             dfs(0, pos);
70             if (ans != -1)
71                 break;
72             deep++;//加深迭代
73         }
74         cout << ans << endl;
75     }
76     return 0;
77 }

View Code

6、ZOJ 2477 Magic Cube 三阶魔方还原(IDA)

　　题意：给出一个打乱的魔方，需要把它还原。

　　思路：

　　　　1、用数组先预先给出12种旋转（6个面，顺逆时针）转的位置编号。

　　　　2、由于题目限制最多5次，对旋转次数进行迭代深搜，如果5次内无法解决，则输出-1.

  1 #include<stdio.h>
  2 #include<string.h>
  3 using namespace std;
  4 int T, deep;
  5 char s[60];
  6 int cent[7] = { 5,23,26,29,32,50 };//第4、0、1、2、3、5面每面中心的编号
  7 int ex[7][9] = { { 1,2,3,4,6,7,8,9 },//第4、0、1、2、3、5面每面除去中心其他的编号
  8 { 10,11,12,22,24,34,35,36 },
  9 { 13,14,15,25,27,37,38,39 },
 10 { 16,17,18,28,30,40,41,42 },
 11 { 19,20,21,31,33,43,44,45 },
 12 { 46,47,48,49,51,52,53,54 }
 13 };
 14 
 15 int get_h()
 16 {
 17     int res = 0;
 18     for (int i = 0; i<6; i++)
 19     {
 20         int c = 0;//该面中和中心颜色不同的数目
 21         for (int j = 0; j<8; j++)
 22         {
 23             if (s[ex[i][j]] != s[cent[i]])     c++;
 24         }
 25         res += c;
 26     }
 27     return res;
 28 }
 29 int wh[10], dd[10];
 30 /*//数组保存位置
 31           1  2  3
 32           4  5  6(第4面)
 33           7  8  9
 34 10 11 12 13 14 15 16 17 18 19 20 21
 35 22 23 24 25 26 27 28 29 30 31 32 33
 36 34 35 36 37 38 39 40 41 42 43 44 45
 37 （第0面）46 47 48（第2面）  （第3面）
 38          49 50 51（第5面）
 39          52 53 54
 40 */
 41 int ope[12][20] = {//用预处理的数组来代替每一种旋转，节约时间。共6个面，每个面顺逆时针，共12种
 42     { 1,4,7,13,25,37,46,49,52,21,33,45,10,11,12,24,36,35,34,22 },//第0面逆时针--
 43     { 45,33,21,1,4,7,13,25,37,52,49,46,34,22,10,11,12,24,36,35 },//          <-|  //两者相互为旋转后的坐标
 44     { 7,8,9,16,28,40,48,47,46,36,24,12,13,14,15,27,39,38,37,25 },//第1面逆时针
 45     { 36,24,12,7,8,9,16,28,40,48,47,46,37,25,13,14,15,27,39,38 },
 46     { 9,6,3,19,31,43,54,51,48,39,27,15,16,17,18,30,42,41,40,28 },//第2面逆时针
 47     { 39,27,15,9,6,3,19,31,43,54,51,48,40,28,16,17,18,30,42,41 },
 48     { 42,30,18,3,2,1,10,22,34,52,53,54,19,20,21,33,45,44,43,31 },//第3面逆时针
 49     { 52,53,54,42,30,18,3,2,1,10,22,34,43,31,19,20,21,33,45,44 },
 50     { 15,14,13,12,11,10,21,20,19,18,17,16,1,2,3,6,9,8,7,4 },//第4面逆时针
 51     { 18,17,16,15,14,13,12,11,10,21,20,19,7,4,1,2,3,6,9,8 },
 52     { 37,38,39,40,41,42,43,44,45,34,35,36,46,47,48,51,54,53,52,49 },//第5面逆时针
 53     { 34,35,36,37,38,39,40,41,42,43,44,45,52,49,46,47,48,51,54,53 }
 54 };
 55 
 56 bool dfs(int d)
 57 {
 58     char maze[60];
 59     int h = get_h();
 60     if (d + (h + 11) / 12 > deep)  return false;
 61     if (h == 0 && d == deep)  return true;
 62     for (int i = 0; i<12; i++)
 63     {
 64         memcpy(maze, s, sizeof(s));
 65         for (int j = 0; j<20; j++)
 66         {
 67             s[ope[i][j]] = maze[ope[i ^ 1][j]];
 68         }
 69         wh[d] = i / 2;
 70         if ((i & 1) == 0)   dd[d] = 1;//奇数为顺时针旋转
 71         else    dd[d] = -1;//偶数为逆时针旋转
 72         if (dfs(d + 1))    return true;
 73         memcpy(s, maze, sizeof(maze));
 74     }
 75 }
 76 
 77 void scan(char &c)
 78 {
 79     char cc;
 80     while (cc = getchar(), cc<'a' || cc>'z');
 81     c = cc;
 82 }
 83 
 84 int main()
 85 {
 86     //freopen("1in","r",stdin) ;
 87     //freopen("1out","w",stdout);
 88     scanf("%d", &T);
 89     while (T--)
 90     {
 91         for (int i = 1; i <= 54; i++)
 92         {
 93             scan(s[i]);
 94         }//以第4、0、1、2、3、5面保存
 95         if (get_h() == 0)//不同数目为0
 96         {
 97             printf("0
"); continue;
 98         }
 99         deep = 1;
100         while (deep <= 5)//迭代深搜
101         {
102             if (dfs(0))  break;
103             deep++;
104         }
105         if (deep > 5)
106         {
107             printf("-1
");
108         }
109         else
110         {
111             printf("%d
", deep);
112             for (int i = 0; i<deep; i++)
113             {
114                 printf("%d %d
", wh[i], dd[i]);
115             }
116         }
117     }
118     return 0;
119 }

View Code

7、hdu 1072 nightmare

　　题意：有个身上绑着炸弹的人，要在迷宫中找到出口。每走一步到相邻位置炸弹倒计时-1，迷宫有若干处有可以重新设置炸弹倒计时的工具，走到那便能重新reset时间，工具被用后就会消失。但是，如果恰好炸弹倒计时为0时，他走到放有工具的地方或者走到出口，则还是会失败。如果能够成功，输出最小的移动步数。

　　思路：BFS。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<memory.h>
 4 #include<queue>
 5 using namespace std;
 6 int n, m;
 7 const int maxn = 10;
 8 int mp[maxn][maxn];
 9 int stx, sty, edx, edy;
10 struct node
11 {
12     int r;
13     int c;
14     int t;
15     int cnt;
16     node(int rr=0,int cc=0,int tt=0,int ct=0):r(rr),c(cc),t(tt),cnt(ct){ }
17 };
18 int ans;
19 int dr[] = { 0,0,1,-1 };
20 int dc[] = { 1,-1,0,0 };
21 void BFS()
22 {
23     queue<node>q;
24     q.push(node(stx, sty, 6));
25     while (!q.empty())
26     {
27         node u = q.front();
28         q.pop();
29         if (u.r == edx&&u.c == edy&&u.t > 0)
30         {
31             ans = u.cnt;
32             return;
33         }
34         if (mp[u.r][u.c] == 4 && u.t > 0) u.t = 6,mp[u.r][u.c]=1;
35         if (u.t == 0)continue;
36         for (int i = 0; i < 4; i++)
37         {
38             int tr = u.r + dr[i];
39             int tc = u.c + dc[i];
40             if (tr < n&&tr >= 0 && tc < m&&tc >= 0)
41             {
42                 if (mp[tr][tc] != 0)
43                 {
44                     q.push(node(tr, tc, u.t - 1, u.cnt + 1));
45                 }
46             }
47         }
48     }
49 }
50 int main()
51 {
52     int T;
53     scanf("%d", &T);
54     while (T--)
55     {
56         scanf("%d%d", &n, &m);
57         for (int i = 0; i < n; i++)
58         {
59             for (int j = 0; j < m; j++)
60             {
61                 scanf("%d", &mp[i][j]);
62                 if (mp[i][j] == 2) stx = i, sty = j;
63                 if (mp[i][j] == 3) edx = i, edy = j;
64             }
65         }
66         ans = -1;
67         BFS();
68         printf("%d
", ans);
69     }
70     return 0;
71 }

View Code

8、HDU 3085 Nightmare Ⅱ (双向BFS)

　　题意：有个迷宫，有两只鬼，每秒可以在周围两步内布满分身，分身也能继续制造分身，直到把迷宫装满（忽略墙）。男孩每秒可以走3步，女孩每秒可以走1步。问男孩能否找到女孩，能则输出最小的时间。

　　思路：男孩和女孩进行双向BFS，同一轮，男孩走3步，女孩走1步，判断是否会被鬼抓到只需判断和两只鬼之间的水平和垂直距离。

  1 //#include<bits/stdc++.h>
  2 #include<iostream>
  3 #include<cstdio>
  4 #include<queue>
  5 using namespace std;
  6 const int maxn = 880;
  7 int n, m;
  8 int dir[4][2] = { 1,0,-1,0,0,1,0,-1 };
  9 char maps[maxn][maxn];
 10 struct node
 11 {
 12     int x, y;
 13 } now, Next, b, g, z[2];
 14 queue <node> q[2], qt;//q[0]为boy，q[1]为girl，qt为当前操作的队列
 15 int step = 0;
 16 void pre_maps()
 17 {
 18     //多组输入，清零
 19     while (!q[0].empty())
 20         q[0].pop();
 21     while (!q[1].empty())
 22         q[1].pop();
 23     while (!qt.empty())
 24         qt.pop();
 25 
 26     int k = 0;
 27     for (int i = 0; i<n; i++)
 28         scanf("%s", maps[i]);
 29     for (int i = 0; i<n; i++)
 30         for (int j = 0; j<m; j++)
 31         {
 32             if (maps[i][j] == 'Z')
 33             {
 34                 z[k].x = i;
 35                 z[k].y = j;
 36                 k++;
 37             }
 38             if (maps[i][j] == 'M')
 39             {
 40                 b.x = i;
 41                 b.y = j;
 42             }
 43             if (maps[i][j] == 'G')
 44             {
 45                 g.x = i;
 46                 g.y = j;
 47             }
 48         }
 49 }
 50 
 51 bool check(node a)
 52 {
 53     if (a.x <0 || a.y <0 || a.x >= n || a.y >= m)//超出地图直接返回
 54         return true;
 55     for (int i = 0; i<2; i++)
 56     {
 57         if (maps[a.x][a.y] == 'X' || (abs(a.x - z[i].x) + abs(a.y - z[i].y)) <= 2 * step)//是墙，或者被鬼抓到返回
 58             return true;
 59     }
 60     return false;
 61 }
 62 bool bfs(int k, int num, char start, char End)
 63 {
 64     qt = q[k];//用来表示当前层的搜索，队列也可以直接赋值
 65     for (int i = 0; i<num; i++)
 66     {
 67         while (!qt.empty())
 68         {
 69             now = qt.front();
 70             qt.pop();
 71             q[k].pop();
 72             if (check(now)) continue;
 73             for (int j = 0; j<4; j++)
 74             {
 75                 Next.x = now.x + dir[j][0];
 76                 Next.y = now.y + dir[j][1];
 77                 if (check(Next)) continue;
 78                 if (maps[Next.x][Next.y] == start) continue;//已经走过了
 79                 if (maps[Next.x][Next.y] == End)//两个bfs相遇
 80                     return true;
 81                 maps[Next.x][Next.y] = start;//走过的地点直接标记
 82                 q[k].push(Next);
 83             }
 84         }
 85         qt = q[k];//将下一层的队列赋值给当前层
 86     }
 87     return false;
 88 }
 89 
 90 int solve()
 91 {
 92     bool flag1 = false, flag2 = false;
 93     step = 0;
 94     q[0].push(b);
 95     q[1].push(g);
 96     while (!q[0].empty() && !q[1].empty())
 97     {
 98         step++;
 99 
100         flag1 = bfs(0, 3, 'M', 'G');//boy的bfs
101         flag2 = bfs(1, 1, 'G', 'M');//girl的bfs
102         if (flag1 || flag2)//当有一方相遇了
103             return step;
104     }
105     return -1;//没有找到
106 }
107 int main()
108 {
109     int t;
110     scanf("%d", &t);
111     while (t--)
112     {
113         scanf("%d%d", &n, &m);
114         pre_maps();
115         printf("%d
", solve());
116     }
117 }

View Code

9、hdu1067-Gap(bfs+哈希)

　　题意：给出初始局面，先把11、21、31、41放在第1、2、3、4行的首位（和0交换），之后每次可以把0左边的数字的大1的数字和0交换（如果0左边为0，则该0不能交换）。问能否到达目标状态，可以的话求出最少最小移动步数。

　　思路：BFS，问题在与如何判重。此处用2^i来构建hash。

  1 #include<iostream>
  2 #include<queue>
  3 #include<set>
  4 using namespace std;
  5 int st[4][8];
  6 long long qz[32];
  7 int des[4][8] = 
  8 {
  9     {11,12,13,14,15,16,17,0},
 10     {21,22,23,24,25,26,27,0},
 11     {31,32,33,34,35,36,37,0},
 12     {41,42,43,44,45,46,47,0}
 13 };
 14 int pos[4][2];
 15 set<long long>vis;
 16 int ans;
 17 
 18 void Pre()
 19 {
 20     qz[0] = 1;
 21     for (int i = 1; i < 32; i++) qz[i] = qz[i - 1] * 2;
 22 }
 23 
 24 long long Hush(int (*s)[8])
 25 {
 26     long long ans = 0;
 27     for (int i = 0; i < 4; i++)
 28     {
 29         for (int j = 0; j < 8; j++) ans +=1ll*qz[i * 8 + j] * s[i][j];
 30     }
 31     return ans;
 32 }
 33 
 34 struct node
 35 {
 36     int p[4][2];//存0的位置
 37     int s[4][8];//存状态
 38     int step;//存步数
 39 };
 40 int BFS()
 41 {
 42     queue<node>q;
 43     node start;
 44     memcpy(start.p, pos, sizeof(pos));
 45     memcpy(start.s, st, sizeof(st));
 46     start.step = 0;
 47     q.push(start);
 48     long long v = Hush(st);
 49     vis.insert(v);
 50     while (!q.empty())
 51     {
 52         node u = q.front();
 53         q.pop();
 54         if (memcmp(u.s, des, sizeof(des)) == 0)
 55         {
 56             return u.step;
 57         }
 58         int tp[4][2];
 59         int ts[4][8];
 60         for (int i = 0; i < 4; i++)
 61         {
 62             memcpy(tp, u.p, sizeof(tp));
 63             memcpy(ts, u.s, sizeof(ts));
 64             int r = tp[i][0];
 65             int c = tp[i][1];
 66             int lv = ts[r][c - 1];
 67             if (lv % 10 == 7||lv==0)continue;
 68             int desr, desc;
 69             int flag = true;
 70             for (int i = 0; flag&&i < 4; i++)
 71             {
 72                 for (int j = 0; j < 8; j++)
 73                 {
 74                     if (ts[i][j] == lv + 1)
 75                     {
 76                         desr = i;
 77                         desc = j;
 78                         flag = false;
 79                     }
 80                 }
 81             }
 82             if (flag)continue;
 83             ts[r][c] = lv + 1;
 84             ts[desr][desc] = 0;
 85             tp[i][0] = desr;
 86             tp[i][1] = desc;
 87             long long tv = Hush(ts);
 88             if (!vis.count(tv))
 89             {
 90                 vis.insert(tv);
 91                 node t;
 92                 memcpy(t.p, tp, sizeof(tp));
 93                 memcpy(t.s, ts, sizeof(ts));
 94                 t.step = u.step + 1;
 95                 q.push(t);
 96             }
 97         }
 98     }
 99     return -1;
100 }
101 void Run()
102 {
103     vis.clear();
104     int cnt = 0;
105     for (int i = 0; i < 4; i++)
106     {
107         for (int j = 1; j < 8; j++)
108         {
109             scanf("%d", &st[i][j]);
110             if (st[i][j] % 10 == 1)
111             {
112                 st[st[i][j] / 10-1][0] = st[i][j];
113                 st[i][j] = 0;
114                 pos[cnt][0] = i;
115                 pos[cnt][1] = j;
116                 cnt++;
117             }
118         }
119     }
120     if (memcmp(st, des, sizeof(des))==0) printf("0
");
121     else printf("%d
", BFS());
122 }
123 int main()
124 {
125     Pre();
126     int t;
127     scanf("%d", &t);
128     while (t--)
129     {
130         Run();
131     }
132     return 0;
133 }

View Code

10、HDU 2102 A计划

　　题意：有个两层的迷宫，骑士需要在T时间内找到公主。传送器可以传到另一层的相同x,y位置，但如果有墙的话会被撞死，如果相同位置都有传送器的话会一直死循环。询问能否找到。

　　思路：BFS，对传送器特判。

 1 #include<iostream>
 2 #include<queue>
 3 using namespace std;
 4 char mz[2][15][15];
 5 bool vis[2][15][15];
 6 int n, m, T;
 7 int edz, edx, edy;
 8 struct node
 9 {
10     int z;
11     int x;
12     int y;
13     int t;
14     node(int zz = 0,int xx=0,int yy=0,int tt=0):z(zz),x(xx),y(yy),t(tt){ }
15 };
16 int dr[] = { 1,-1,0,0 };
17 int dc[] = {0, 0, 1, -1};
18 bool BFS()
19 {
20     memset(vis, 0, sizeof(vis));
21     queue<node>q;
22     q.push(node(0, 0, 0, 0));
23     vis[0][0][0] = true;
24     while (!q.empty())
25     {
26         node u = q.front();
27         q.pop();
28         if (u.z == edz&&u.x == edx&&u.y == edy&&u.t <= T)
29         {
30             return true;
31         }
32         if (u.t > T) return false;
33         for (int i = 0; i < 4; i++)
34         {
35             int tr = u.x + dr[i];
36             int tc = u.y + dc[i];
37             if (tr < n&&tr >= 0 && tc < m&&tc >= 0 && mz[u.z][tr][tc] != '*' && !vis[u.z][tr][tc])
38             {
39                 if (mz[u.z][tr][tc] != '#')
40                 {
41                     vis[u.z][tr][tc] = true;
42                     q.push(node(u.z, tr, tc, u.t + 1));
43                 }
44                 else
45                 {
46                     vis[!u.z][tr][tc] = vis[u.z][tr][tc] = true;
47                     if (mz[!u.z][tr][tc] != '*'&&mz[!u.z][tr][tc] != '#')
48                     {
49                         q.push(node(!u.z, tr, tc, u.t + 1));
50                     }
51                 }
52             }
53         }
54 
55     }
56     return false;
57 }
58 int main()
59 {
60     int C;
61     scanf("%d", &C);
62     while (C--)
63     {
64         scanf("%d%d%d", &n, &m,&T);
65         for (int i = 0; i < 2; i++)
66         {
67             for (int j = 0; j < n; j++)
68             {
69                 for (int k = 0; k < m; k++)
70                 {
71                     cin >> mz[i][j][k];
72                     if (mz[i][j][k] == 'P')
73                     {
74                         edz = i;
75                         edx = j;
76                         edy = k;
77                     }
78                 }
79             }
80         }
81         if (BFS()) printf("YES
");
82         else printf("NO
");
83     }
84     return 0;
85 }

View Code

11、J - Travelling hdu 3001 BFS+状压

　　题意：求走遍所有城市的最小花费。每座城市最多经过两次。

　　思路：BFS。3进制来表示某座城市经过几次。

  1 //bfs + 状态压缩：开始时把每一个点都入队，模拟3进制处理每个状态，最后 + 优化。
  2 #include<iostream>
  3 #include<stdio.h>
  4 #include<math.h>
  5 #include<string.h>
  6 #include<algorithm>
  7 #include<iostream>
  8 #include<queue>
  9 using namespace std;
 10 #define N 12//最多12个城市
 11 #define LL long long
 12 const int inf = 0x3fffffff;//最大值
 13 int g[N][N];
 14 int n, m, ans;
 15 int mark[N][60000];//3^10=59064  j状态下走到i的时间
 16 struct node
 17 {
 18     int x, t, s, cnt;  //位置、时间、状态、个数
 19     friend bool operator<(node a, node b)
 20     {
 21         return a.t>b.t;
 22     }
 23 };
 24 int gettmp(int x, int k)  //得到X在3进制下的第K位是多少
 25 {                        //判断该点是否经过了，经过了几次
 26     int t;
 27     while (x)
 28     {
 29         t = x % 3;
 30         k--;
 31         if (k == 0)
 32             break;
 33         x /= 3;
 34     }
 35     return k ? 0 : t;
 36 }
 37 void inti()//初始化数组
 38 {
 39     int i, j;
 40     for (i = 1; i <= n; i++)
 41     {
 42         for (j = 0; j<(int)pow(3, n); j++)
 43             mark[i][j] = inf;
 44     }
 45 }
 46 void bfs()
 47 {
 48     int i;
 49     priority_queue<node>q;//时间小的优先级高
 50     node cur, next;
 51     for (i = 1; i <= n; i++)
 52     {//一开始把每个点都加入队列
 53         cur.x = i;
 54         cur.s = pow(3, (i - 1));//状态，表示只有该点走过
 55         cur.t = 0;
 56         cur.cnt = 1;//经过城市一个
 57         q.push(cur);
 58         mark[i][0] = 0;
 59     }
 60     while (!q.empty())
 61     {
 62         cur = q.top();
 63         q.pop();
 64         for (i = 1; i <= n; i++)
 65         {
 66             if (g[cur.x][i] == inf)  //此路不通
 67                 continue;
 68             next.cnt = cur.cnt;
 69             next.s = cur.s;
 70             next.t = cur.t + g[cur.x][i];
 71             if (ans<next.t)    //优化很重要
 72                 continue;
 73             next.x = i;
 74             int t = gettmp(next.s, i);  //该点经过了几次，
 75             if (t >= 2)                 //经过2次后就不能走了
 76                 continue;
 77             next.s += pow(3, (i - 1));    //该点经过次数加一
 78             if (t == 0)                 //经过一个新景点
 79             {
 80                 next.cnt++;
 81                 if (next.cnt == n)
 82                 {
 83                     ans = min(ans, next.t);
 84                     continue;
 85                 }
 86             }
 87             if (next.t<mark[i][next.s])
 88             {
 89                 mark[i][next.s] = next.t;
 90                 q.push(next);
 91             }
 92         }
 93     }
 94 }
 95 int main()
 96 {
 97     int a, b, c, i, j;
 98     while (scanf("%d%d", &n, &m) != -1)
 99     {
100         for (i = 0; i <= n; i++)
101             for (j = 1; j <= n; j++)
102                 g[i][j] = (i == j ? 0 : inf);
103         for (i = 0; i<m; i++)
104         {
105             scanf("%d%d%d", &a, &b, &c);
106             g[a][b] = g[b][a] = min(g[a][b], c);//考虑到重边
107         }
108         ans = inf;
109         inti();
110         bfs();
111         if (ans == inf)
112             ans = -1;
113         printf("%d
", ans);
114     }
115     return 0;
116 }

View Code