搜索基础题

1.http://acm.hdu.edu.cn/showproblem.php?pid=1312

题意：在一个仅有红黑格子组成的矩形中，一个人只能走上下左右相邻黑色格子，问从起点开始共能走多少个格子？

’#‘：红色格子

’.'：黑色格子；

’@‘：起点　

BFS 和 DFS 都可以遍历所有走的点，每次走过一点时，计数++即可；

2.http://acm.hdu.edu.cn/showproblem.php?pid=1728

由题可知，在限制转弯数量的前提下能够从一点走到另一个点即可；BFS 和 DFS都能求出解。我 DFS 还没实现

需要注意：1.点坐标是从 1 开始的。

　　　　　2.最短的路径可能不满足转弯数的限制。

　　　　　3.起点与终点重合。

超内存代码：已找到原因，完全是大意所致。贴在此处，希望自己以后再看时能一眼找到。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 #define N 105
 6 
 7 struct Pos
 8 {
 9     int x, y;
10     int turn;
11     int dire;
12 }S, E;
13 char map[N][N];
14 bool used[N][N][12][4];
15 int dir[][2]={1,0, -1,0, 0,1, 0,-1};
16 int n, m, k;
17 
18 bool Judge (Pos s)
19 {
20     if (s.x>=1 && s.x<=m && s.y>=1 && s.y<=n && map[s.x][s.y]=='.' && !used[s.x][s.y][S.turn][S.dire] && s.turn <= k)
21         return true;
22     return false;
23 }
24 
25 bool  bfs ()
26 {
27     Pos Pre, Cur;
28     queue <Pos> Q;
29     while (!Q.empty ()) Q.pop();
30     memset (used, 0, sizeof used);
31 
32     S.dire = -1;
33     S.turn = 0;
34     used[S.x][S.y][S.turn][S.dire] = true;
35     Q.push (S);
36     while (!Q.empty ())
37     {
38         Pre = Q.front ();
39         Cur = Pre;
40         Q.pop();
41         if (Cur.x==E.x && Cur.y==E.y)
42             return true;
43         for(int i=0; i<4; i++)
44         {
45             Cur.x = Pre.x + dir[i][0];
46             Cur.y = Pre.y + dir[i][1];
47             Cur.turn = Pre.turn;
48             Cur.dire = i;
49             if (Cur.dire != Pre.dire && Pre.dire !=-1)
50                 Cur.turn++;
51             if (Judge (Cur))
52             {
53                 used[Cur.x][Cur.y][Cur.turn][Cur.dire] = true;
54                 Q.push (Cur);
55             }
56         }
57     }
58     return false;
59 }
60 
61 int main ()
62 {
63     int t;
64 //    freopen ("test.txt","r",stdin);
65     scanf ("%d",&t);
66     while (t--)
67     {
68         scanf ("%d%d",&m, &n);
69         for (int i=1; i<=m; i++)
70             for (int j=1; j<=n; j++)
71                 scanf (" %c", map[i]+j);
72         scanf ("%d%d%d%d%d",&k, &S.y, &S.x, &E.y, &E.x);
73 
74         puts ((bfs ()?"yes":"no"));
75     }
76     return 0;
77 }

View Code

BFS代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 #define N 105
 6 
 7 struct Pos
 8 {
 9     int x, y;
10     int turn;
11 }S, E;
12 char map[N][N];
13 bool used[N][N];
14 int dir[][2]={1,0, -1,0, 0,1, 0,-1};
15 int n, m, k;
16 
17 bool Judge (Pos s)
18 {
19     if (s.x>=1 && s.x<=m && s.y>=1 && s.y<=n && map[s.x][s.y]=='.')
20         return true;
21     return false;
22 }
23 
24 bool  bfs ()
25 {
26     Pos Pre, Cur;
27     queue <Pos> Q;
28     while (!Q.empty ()) Q.pop();
29     memset (used, 0, sizeof used);
30 
31     S.turn = -1;   //第一次不能算作转弯
32     used[S.x][S.y] = true;
33     Q.push (S);
34     while (!Q.empty ())
35     {
36         Pre = Q.front ();
37         Cur = Pre;
38         Q.pop();
39         if (Pre.x == E.x && Pre.y==E.y && Pre.turn<=k)
40           return true;
41         for(int i=0; i<4; i++)
42         {
43             Cur.x = Pre.x + dir[i][0];
44         Cur.y = Pre.y + dir[i][1];
45         while (Judge (Cur))   //每次选定一个方向遍历到底。
46         {
47             if (!used[Cur.x][Cur.y])
48             {
49                 used[Cur.x][Cur.y] = true;
50                 Cur.turn = Pre.turn + 1;
51                 Q.push (Cur);
52                 if (Cur.x == E.x && Cur.y == E.y)
53                 {
54                     if (Cur.turn <= k)
55                         return true;
56                     continue;
57                 }
58             }
59             Cur.x += dir[i][0];
60             Cur.y += dir[i][1];
61         }
62         }
63     }
64     return false;
65 }
66 
67 int main ()
68 {
69     int t;
70     freopen ("test.txt","r",stdin);
71     scanf ("%d",&t);
72     while (t--)
73     {
74         scanf ("%d%d",&m, &n);
75         for (int i=1; i<=m; i++)
76             for (int j=1; j<=n; j++)
77                 scanf (" %c", map[i]+j);
78         scanf ("%d%d%d%d%d",&k, &S.y, &S.x, &E.y, &E.x);
79 
80         puts ((bfs ()?"yes":"no"));
81     }
82     return 0;
83 }

View Code

3.http://poj.org/problem?id=3278

题意：在一条直线上站着一个人和一头奶牛，人有三种移动方式（+1 ，-1， *2），问怎么移动可以使移动次数最小就可以到达奶牛的位置；

分析：因为要你求最小的移动步数，即最优解。用 BFS 在一条直线上搜索一遍，那搜到奶牛时一定会是经过最小的步数。

BFS：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 #define N 100005
 6 
 7 struct Pos
 8 {
 9     int x;
10     int step;
11 };
12 bool used[N];
13 int n, k;
14 int bfs ()
15 {
16     queue <Pos> Q;
17     while (!Q.empty ()) Q.pop();
18     memset (used, 0, sizeof used);
19 
20     Pos s, cur;
21     s.x = n; s.step = 0;
22     used[s.x] = true;
23     Q.push (s);
24     while (!Q.empty ())
25     {
26         Pos pre = Q.front();
27         Q.pop();
28         for (int i=0; i<3; i++)
29         {
30             if (i==0)
31                 cur.x = pre.x + 1;
32             else if (i==1)
33                 cur.x = pre.x - 1;
34             else
35                 cur.x = pre.x * 2;
36             if (cur.x<0 || cur.x>100000 || used[cur.x])
37                 continue;
38             cur.step = pre.step + 1;
39             if (cur.x == k)
40                 return cur.step;
41             used[cur.x]=true;
42             Q.push (cur);
43         }
44     }
45     return -1;
46 }
47 
48 int main ()
49 {
50     while (~scanf ("%d%d",&n, &k))
51     {
52         if (n > k)
53             printf ("%d
",n-k);
54         else if (n==k)
55             printf ("0
");
56         else
57         printf ("%d
",bfs ());
58     }
59     return 0;
60 }

View Code

4.http://acm.hdu.edu.cn/showproblem.php?pid=1016

题意：给你n个数，n个数围城一个圆环，任何连个相邻的数的都都是素数，输出所有的组合。

分析：题目要求输出所有满足条件的组合，即所有解。故用DFS可行。和n皇后问题基本一样的。

DFS：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 using namespace std;
 5 
 6 int d[21], n;
 7 int used[21];
 8 bool prime[45];
 9 
10 bool isprime (int n)
11 {
12     int len = sqrt(n);
13     for (int i=2; i<=len; i++)
14         if (n%i==0)
15             return false;
16     return true;
17 }
18 
19 void makeprime ()
20 {
21     memset (prime, 0, sizeof prime);
22     for (int i=2; i<=44; i++)
23         if (isprime(i))
24             prime[i] = true;
25 }
26 void dfs (int cur)
27 {
28     if (cur > n)
29     {
30         if (prime[d[1]+d[n]])
31         {
32             for (int i=1; i<n; i++)
33                 printf ("%d ",d[i]);
34             printf ("%d
",d[n]);
35         }
36         return;
37     }
38     for (int i=2; i<=n; i++)
39     {
40         d[cur] = i;
41         if (!prime[d[cur]+d[cur-1]] || used[i]) continue;
42         used[i] = true;
43         dfs (cur+1);
44         used[i] = false;
45     }
46 }
47 int main ()
48 {
49     int lp=0;
50     makeprime();
51     while (~scanf ("%d",&n))
52     {
53         printf ("Case %d:
",++lp);
54         memset (used, 0, sizeof used);
55         if ((n&1))
56         {
57             puts("");
58             continue;
59         }
60         d[1] = 1;
61         used[1] = true;
62         dfs (2);
63         puts("");
64     }
65     return 0;
66 }

View Code

5.http://acm.hdu.edu.cn/showproblem.php?pid=1241

题意：给你一个矩形，其中‘@’代表油点，孤立的连通油点组成一个油田，问你有多少个油田？

分析：先由两重for循环找到所有的可能的没有被标记的油点，再由一个DFS/BFS来标记出一个连通的油田，DFS/BFS次数即是油田的次数；

DFS代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 #define N 105
 5 
 6 char map[N][N];
 7 int dir[][2]={1,0, -1,0, 0,1, 0,-1, 1,1, -1,-1, 1,-1, -1,1};
 8 int n, m, sum;
 9 bool used[N][N];
10 
11 void dfs (int x, int y)
12 {
13     if (x<0||x>n-1 || y<0||y>m-1 || map[x][y]=='*' || used[x][y]) return;
14     used[x][y] = true;
15     for (int i=0; i<8; i++)
16         dfs (x+dir[i][0], y+dir[i][1]);
17 }
18 
19 void Sloved ()
20 {
21     int ans = 0;
22     memset (used, 0, sizeof used);
23     for (int i=0; i<n; i++)
24         for (int j=0; j<m; j++)
25             if (map[i][j]=='@' && !used[i][j])
26             {
27                 ans++;
28                 dfs (i,j);
29             }
30     printf ("%d
",ans);
31 }
32 int main ()
33 {
34     while (~scanf ("%d%d",&n, &m) && n+m)
35     {
36         for (int i=0; i<n; i++)
37             for (int j=0; j<m; j++)
38                 scanf (" %c",map[i]+j);
39 
40         Sloved ();
41     }
42     return 0;
43 }

View Code

BFS代码：有一点点改动，时间竟然还更多了 ………

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 #define N 105
 6 
 7 struct Pos
 8 {
 9     int x, y;
10 }oil[N*N];
11 char map[N][N];
12 int dir[][2]={1,0, -1,0, 0,1, 0,-1, 1,1, -1,-1, 1,-1, -1,1};
13 int n, m;
14 bool used[N][N];
15 
16 bool judge (Pos s)
17 {
18     if (s.x<0||s.x>n-1 || s.y<0||s.y>m-1 || used[s.x][s.y] || map[s.x][s.y]=='*')
19         return false;
20     return true;
21 }
22 
23 void bfs (Pos a)
24 {
25     queue <Pos> Q;
26 
27     used[a.x][a.y] = true;
28     Q.push (a);
29     while (!Q.empty ())
30     {
31         Pos Pre = Q.front();
32         Q.pop();
33         for (int i=0; i<8; i++)
34         {
35             Pos Cur = Pre;
36             Cur.x += dir[i][0];
37             Cur.y += dir[i][1];
38             if (judge (Cur))
39             {
40                 used[Cur.x][Cur.y] = true;
41                 Q.push (Cur);
42             }
43         }
44     }
45 }
46 int main ()
47 {
48     while (~scanf ("%d%d",&n, &m) && n+m)
49     {
50         int k=0;
51         for (int i=0; i<n; i++)
52             for (int j=0; j<m; j++)
53             {
54                 scanf (" %c",map[i]+j);
55                 if (map[i][j]=='@')
56                 {
57                     oil[k].x = i;
58                     oil[k].y = j;
59                     k++;
60                 }
61             }
62         memset (used, 0, sizeof used);
63         int sum=0;
64         for (int i=0; i<k; i++)
65         {
66             if (used[oil[i].x][oil[i].y])
67                 continue;
68             bfs(oil[i]);
69             sum ++;
70         }
71         printf ("%d
",sum);
72     }
73     return 0;
74 }

View Code

6.http://acm.hdu.edu.cn/showproblem.php?pid=1548

题意：有个奇怪的电梯，里面只有上下两个按钮，并且每层楼都有一个数字K_i，代表可以向上升K_i 层或向下下降K_i层，要你输出从A层到B层最少需要按按钮的次数，若不可达，则输出-1。

分析：明显，题目是要求最小的按钮次数，即最优解。我们可以用BFS解答。但我们应该可以通过DFS每次选最小的次数来控制最优解获得答案，无奈一直超内存。。

超内存代码：不知为何超内存。}}}}}

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 #define Min(a, b) (a < b ? a:b)
 5 #define INF 0x3f3f3f3f
 6 
 7 int ans, n, m, a, b, k[205];
 8 bool used[205];
 9 
10 void dfs (int cur, int step)
11 {
12     if (cur == b)
13     {
14         ans = Min (ans, step);
15         return;
16     }
17     for (int i=0; i<2; i++)
18     {
19         int next = cur + (i ? -k[cur]:k[cur]);
20         if (next>n || cur<1) continue; //因为结果老是超内存，故把判断加在此处，但还是超内存
21         if (used[next]) continue;
22         used[next] = true;
23         dfs (next, step+1);
24     }
25 }
26 int main ()
27 {
28     while (~scanf ("%d",&n) && n)
29     {
30         scanf ("%d%d",&a, &b);
31         for (int i=1; i<=n; i++)
32             scanf ("%d",&k[i]);
33 
34         if (a == b)
35         {
36             printf ("0
");
37             continue;
38         }
39         if (a<1||a>n || b<1||b>n)
40         {
41             printf ("-1
");
42             continue;
43         }
44         memset (used, 0, sizeof used);
45         ans = INF;
46         dfs (a, 0);
47         printf ("%d
",ans!=INF ? ans:-1);
48     }
49     return 0;
50 }

View Code

BFS：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 #define INF 0x3f3f3f3f
 6 
 7 struct Node
 8 {
 9     int floor;
10     int step;
11 }A, B;
12 int n, m, k[205];
13 bool used[205];
14 
15 int bfs ()
16 {
17     queue <Node> Q;
18     Node Pre, Cur;
19     while (!Q.empty ()) Q.pop();
20 
21     memset (used, 0, sizeof used);
22 
23     used[A.floor] = true;
24     A.step = 0;
25     Q.push (A);
26     while (!Q.empty())
27     {
28         Pre = Q.front ();
29         Q.pop();
30         if (Pre.floor == B.floor)
31             return Pre.step;
32 
33         for (int i=0; i<2; i++)
34         {
35             Cur.floor = Pre.floor + (i?-1:1)*k[Pre.floor];
36             Cur.step = Pre.step + 1;
37             if (Cur.floor<1 || Cur.floor>n || used[Cur.floor])
38                 continue;
39             used[Cur.floor] = true;
40             Q.push (Cur);
41         }
42     }
43     return -1;
44 }
45 
46 int main ()
47 {
48     while (~scanf ("%d",&n) && n)
49     {
50         scanf ("%d%d",&A.floor, &B.floor);
51         for (int i=1; i<=n; i++)
52             scanf ("%d",&k[i]);
53         int ans = bfs ();
54         printf ("%d
",ans);
55     }
56     return 0;
57 }

View Code

7.http://acm.hdu.edu.cn/showproblem.php?pid=1253

分析：纯粹的搜索题，只是从二维扩展到三维，增加了两个方向而已；

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 #define N 55
 6 
 7 struct Pos
 8 {
 9     int x, y, z;
10     int step;
11 };
12 int map[N][N][N], a, b, c, t;
13 bool used[N][N][N];
14 int dir[][3]={0,0,1, 0,0,-1, 1,0,0, -1,0,0, 0,1,0, 0,-1,0};
15 
16 bool judge (Pos cur)
17 {
18     if (cur.x>=0&&cur.x<a && cur.y>=0&&cur.y<b && cur.z>=0&&cur.z<c &&
19          !used[cur.x][cur.y][cur.z] && !map[cur.x][cur.y][cur.z] && cur.step <= t)
20         return true;
21     return false;
22 }
23 
24 int bfs ()
25 {
26     queue <Pos> Q;
27     while (!Q.empty ()) Q.pop();
28     memset (used, 0, sizeof used);
29     Pos Pre, Cur;
30     Pre.x = Pre.y = Pre.z = Pre.step = 0;
31     used[0][0][0] = true;
32     Q.push (Pre);
33     while (!Q.empty ())
34     {
35         Pre = Q.front ();
36         Q.pop();
37         for (int i=0; i<6; i++)
38         {
39             Cur = Pre;
40             Cur.x += dir[i][0];
41             Cur.y += dir[i][1];
42             Cur.z += dir[i][2];
43             Cur.step += 1;
44             if (judge (Cur))
45             {
46                 if (Cur.x==a-1 && Cur.y==b-1 && Cur.z==c-1)
47                     return Cur.step;
48                 used[Cur.x][Cur.y][Cur.z] = true;
49                 Q.push (Cur);
50             }
51         }
52     }
53     return -1;
54 }
55 int main()
56 {
57     int k;
58     scanf ("%d",&k);
59     while (k--)
60     {
61         scanf ("%d%d%d%d",&a, &b, &c, &t);
62         for (int  i=0; i<a; i++)
63             for (int j=0; j<b; j++)
64                 for (int k=0; k<c; k++)
65                     scanf ("%d",&map[i][j][k]);
66         printf ("%d
",bfs());
67     }
68     return 0;
69 }

View Code

DFS代码：我觉得应该是超时还差不多，可是最后变成超内存，我就不知为何了？留着供以后检查。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 #define N 55
 6 #define INF 0x3f3f3f3f
 7 #define Min(a, b) (a < b ? a : b)
 8 
 9 int map[N][N][N], a, b, c, t, ans;
10 bool used[N][N][N];
11 int dir[][3]={0,0,1, 0,0,-1, 1,0,0, -1,0,0, 0,1,0, 0,-1,0};
12 
13 
14 void dfs (int x, int y, int z, int step)
15 {
16     if (x<0||x>a-1 || y<0||y>b-1 || z<0||z>c-1 || map[x][y][z])
17         return;
18     if (step >= ans || step > t)
19         return;
20     if (x==a-1 && y==b-1 && z==c-1)
21     {
22         ans = Min(ans, step);
23         return;
24     }
25     for (int i=0; i<6; i++)
26     {
27         int xx = x + dir[i][0];
28         int yy = y + dir[i][1];
29         int zz = z + dir[i][2];
30         if (used[xx][yy][zz]) continue;
31 
32         used[xx][yy][zz] = true;
33         dfs (xx, yy, zz, step+1);
34     }
35 }
36 
37 int main()
38 {
39     int k;
40     scanf ("%d",&k);
41     while (k--)
42     {
43         scanf ("%d%d%d%d",&a, &b, &c, &t);
44         for (int  i=0; i<a; i++)
45             for (int j=0; j<b; j++)
46                 for (int k=0; k<c; k++)
47                     scanf ("%d",&map[i][j][k]);
48         ans = INF;
49         memset (used, 0, sizeof used);
50         used[0][0][0] = true;
51         dfs (0, 0, 0, 0);
52         printf ("%d
",ans==INF ? -1:ans);
53     }
54     return 0;
55 }

View Code

8.http://acm.hdu.edu.cn/showproblem.php?pid=1242

题意：公主被魔王抓到地牢里去了，为了防止被人就走，魔王派兵在某些位置守住了，要杀死这些士兵得花费一分钟时间，现在公主的朋友要去救她（题目貌似暗示有很多人去救，可我从‘r'开始搜也能ac ，时间还更优，无语了。。）；

分析：纯粹搜索题，让你求最优解，故容易想到用bfs。不过同样的，大多数bfs可以解决的dfs也是可以解决的。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 #define N 205
 5 using namespace std;
 6 
 7 struct Pos
 8 {
 9     int x, y; 
10     int step;
11 }S;
12 char map[N][N];
13 bool used[N][N];
14 int dir[][2]={1,0, -1,0, 0,1, 0,-1};
15 int n, m;
16 bool Judge (Pos a)
17 {
18     if (a.x<0||a.x>n-1 || a.y<0||a.y>m-1 || map[a.x][a.y]=='#' || used[a.x][a.y])
19         return false;
20     return true;
21 }
22 
23 int bfs ()
24 {
25     Pos Pre, Cur;
26     queue <Pos> Q;
27     while (!Q.empty ()) Q.pop();
28     memset (used, 0, sizeof used);
29     used[S.x][S.y] = true;
30     Q.push (S);
31     while (!Q.empty ())
32     {
33         Pre = Q.front ();
34         Q.pop();
35         for (int i=0; i<4; i++)
36         {
37             Cur = Pre;
38             Cur.x += dir[i][0];
39             Cur.y += dir[i][1];
40             Cur.step += 1;
41             if (Judge (Cur))
42             {
43                 if (map[Cur.x][Cur.y] == 'r')
44                     return Cur.step;
45                 if (map[Cur.x][Cur.y]=='x')
46                     Cur.step++;
47                 used[Cur.x][Cur.y] = true;
48                 Q.push (Cur);
49             }
50         }
51     }
52     return -1;
53 }
54 int main ()
55 {
56     while (~scanf ("%d%d",&n, &m))
57     {
58         for (int i=0; i<n; i++)
59             for (int j=0; j<m; j++)
60             {
61                 scanf (" %c",map[i]+j);
62                 if (map[i][j] == 'a')
63                     S.x = i, S.y = j;
64             }
65         int ans = bfs ();
66         if (ans == -1)
67             puts ("Poor ANGEL has to stay in the prison all his life.");
68         else
69             printf ("%d
",ans);
70     }
71     return 0;
72 }

View Code

DFS代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 #define Min(a, b) (a < b ? a : b)
 5 #define N 205
 6 #define INF 0x3f3f3f3f
 7 using namespace std;
 8 
 9 char map[N][N];
10 bool used[N][N];
11 int dir[][2]={1,0, -1,0, 0,1, 0,-1};
12 int n, m, ans;
13 
14 void dfs (int x, int y, int step)
15 {
16     if (x<0||x>n-1 || y<0||y>m-1 || map[x][y]=='#')
17         return;
18     if(step>=ans)
19         return;
20     if (map[x][y]=='x')
21         step++;
22     if (map[x][y]=='r')
23     {
24         ans = Min(ans, step);
25         return;
26     }
27     for (int i=0; i<4; i++)
28     {
29         int xx = x + dir[i][0];
30         int yy = y + dir[i][1];
31         if (used[xx][yy]) continue;
32         used[xx][yy] = true;
33         dfs (xx, yy, step+1);
34         used[xx][yy] = false;  /////////////////////////////////
35     }
36 }
37 
38 int main ()
39 {
40     int x, y;
41     while (~scanf ("%d%d",&n, &m))
42     {
43         for (int i=0; i<n; i++)
44             for (int j=0; j<m; j++)
45             {
46                 scanf (" %c",map[i]+j);
47                 if (map[i][j] == 'a')
48                     x = i, y = j;
49             }
50 
51         ans = INF;
52         memset (used, 0,sizeof used);
53         used[x][y] = true;
54         dfs (x, y, 0);
55         if (ans == INF)
56             puts ("Poor ANGEL has to stay in the prison all his life.");
57         else
58             printf ("%d
",ans);
59     }
60     return 0;
61 }

View Code

9.http://acm.hdu.edu.cn/showproblem.php?pid=1072

题意：I 做了一个噩梦，他梦到自己在一个迷宫里面，并且身上绑了个初始值是 6 的定时炸弹哥，现在 I 从编号为 2 的位置开始走，并且若在时间不为0之前遇到编号为 4（可以使用任意次）的位置时，炸弹上的时间可以自动重置为 6，要求输出到达出口（编号为 3 的位置）的最少时间？若不能到达出口，则输出 -1；

分析：一般最优解都趋于用BFS 解答，不过我自己为了练习下 DFS，我分别用 BFS 和 DFS写了两次；

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <cmath>
 5 #define Min(a, b) (a < b ? a : b)
 6 #define INF 0x3f3f3f3f
 7 
 8 const int MAX = 9;
 9 
10 int dir[4][2]={1,0,-1,0,0,1,0,-1};
11 
12 int map[MAX][MAX],dist[MAX][MAX],time[MAX][MAX];
13 int n,m,sx,sy,ans;
14 
15 void dfs (int x, int y, int step, int res)
16 {
17     if (x<0||x>n-1 || y<0||y>m-1 || map[x][y]==0)
18         return;
19     
20     if (res<=0 || step>=ans)
21         return;
22     if (map[x][y]==3)
23     {
24         ans = Min(ans, step);
25         return;
26     }
27     if (map[x][y]==4)
28         res = 6;
29     if (step>=dist[x][y] && time[x][y]>=res)
30         return;
31     dist[x][y] = step;
32     time[x][y] = res;
33 
34     for (int i=0; i<4; i++)
35     {
36         int xx = x + dir[i][0];
37         int yy = y + dir[i][1];
38         
39         dfs (xx, yy, step+1, res-1);
40     }
41 }
42 
43 int main(){
44 
45 //    freopen ("test.txt","r",stdin);
46     int t, x, y;
47     scanf ("%d",&t);
48     while(t--)
49     {
50         scanf ("%d%d",&n, &m);
51         for (int i=0; i<n; i++)
52             for (int j=0; j<m; j++)
53             {
54                 scanf ("%d",map[i]+j);
55                 dist[i][j] = INF;
56                 if (map[i][j]==2)
57                     x = i, y = j;
58             }
59         memset (time, 0, sizeof time);
60         ans = INF;
61         dfs (x, y, 0, 6);
62         printf ("%d
",ans==INF ? -1 : ans);
63     }
64     
65     return 0;
66 }

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 
 6 struct Pos
 7 {
 8     int x, y;
 9     int res, step, dire;
10 }S, E;
11 int map[15][15], m, n;
12 int used[15][15][4];
13 int dir[][2]={1,0, -1,0, 0,1, 0,-1};
14 
15 bool judge (Pos cur)
16 {
17     if (cur.x<0||cur.x>n-1 || cur.y<0||cur.y>m-1 || map[cur.x][cur.y]==0 || cur.res<=0 || used[cur.x][cur.y][cur.dire]>4)
18         return false;
19     return true;
20 }
21 
22 int bfs ()
23 {
24     Pos Pre, Cur;
25     queue <Pos> Q;
26     while (!Q.empty ()) Q.pop();
27     memset (used, 0, sizeof used);
28     
29     S.step = 0;
30     S.res = 6;
31     S.dire = -1;
32     used[S.x][S.y][S.dire]++;
33     Q.push (S);
34     while (!Q.empty ())
35     {
36         Pre = Q.front ();
37         Q.pop();
38         for (int i=0; i<4; i++)
39         {
40             Cur = Pre;
41             Cur.x += dir[i][0];
42             Cur.y += dir[i][1];
43             Cur.step += 1;
44             Cur.res -= 1;
45             Cur.dire = i;
46             if (judge (Cur))
47             {
48                 if (map[Cur.x][Cur.y]==3)
49                     return Cur.step;
50                 if (map[Cur.x][Cur.y]==4)
51                     Cur.res = 6;
52                 used[Cur.x][Cur.y][Cur.dire]++;
53                 Q.push (Cur);
54             }
55         }
56     }
57     return -1;
58 }
59 int main()
60 {
61     int t;
62 //    freopen ("test.txt","r",stdin);
63     scanf ("%d",&t);
64     while (t--)
65     {
66         scanf ("%d%d",&n, &m);
67         for (int i=0; i<n; i++)
68             for (int j=0; j<m; j++)
69             {
70                 scanf ("%d",map[i]+j);
71                 if (map[i][j] == 2)
72                     S.x = i, S.y = j;
73             }
74         printf ("%d
",bfs());
75     }
76     return 0;
77 }

View Code

10.http://acm.hdu.edu.cn/showproblem.php?pid=2102

分析：同样是一道bfs纯搜索题。只是有个地方需要注意，在传输机#对面还是传输机#的情况，相当于陷入无止境的传输过程中，是不能走的，故把这两个地方当做墙处理。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 
 6 
 7 struct Pos
 8 {
 9     int x, y, z;
10     int step;
11 }S, E;
12 char map[2][15][15];
13 bool used[2][15][15];
14 int dir[][2]={1,0, -1,0, 0,1, 0,-1};
15 int n, m, t;
16 bool bfs ()
17 {
18     Pos Pre, Cur;
19     queue <Pos> Q;
20     while (!Q.empty ()) Q.pop();
21     memset (used, 0, sizeof used);
22 
23     used[S.z][S.x][S.y] = true;
24     Q.push (S);
25     while (!Q.empty ())
26     {
27         Pre = Q.front ();
28         Q.pop();
29         for (int i=0; i<4; i++)
30         {
31             Cur = Pre;
32             Cur.x += dir[i][0];
33             Cur.y += dir[i][1];
34             Cur.step += 1;
35             if (Cur.x>=0 && Cur.x<n && Cur.y>=0 && Cur.y<m && Cur.step<=t)
36             {
37                 if (map[Cur.z][Cur.x][Cur.y]=='#')
38                 {
39                     Cur.z ^= 1;
40                     if (map[Cur.z][Cur.x][Cur.y]=='#')
41                         map[Cur.z][Cur.x][Cur.y] = map[Cur.z^1][Cur.x][Cur.y] = '*';
42                 }
43                 if (map[Cur.z][Cur.x][Cur.y]=='*' || used[Cur.z][Cur.x][Cur.y]) continue;
44                 if (map[Cur.z][Cur.x][Cur.y]=='P')
45                     return true;
46                 used[Cur.z][Cur.x][Cur.y] = true;
47                 Q.push (Cur);
48             }
49         }
50     }
51     return false;
52 }
53 
54 void MakeMap ()
55 {
56     for (int i=0; i<n; i++)
57         for (int j=0; j<m; j++)
58         {
59             scanf (" %c", map[0][i]+j);
60             if (map[0][i][j]=='S')
61             {
62                 S.x = i, S.y = j;
63                 S.z = 0;
64                 S.step = 0;
65             }
66         }
67     for (int i=0;i<n; i++)
68         for (int j=0; j<m; j++)
69         {
70             scanf (" %c",map[1][i]+j);
71             if (map[1][i][j]=='S')
72             {
73                 S.x = i, S.y = j;
74                 S.z = 1;
75                 S.step = 0;
76             }
77         }
78 }
79 
80 int main()
81 {
82     int k;
83     scanf ("%d",&k);
84     while (k--)
85     {
86         scanf ("%d%d%d",&n, &m, &t);
87         
88         MakeMap ();
89 
90         puts (bfs () ? "YES" : "NO");
91 
92     }
93     return 0;
94 }

View Code

我用dfs做了下，杀毒软件一直报错，无法运行。先留着，以后再找bugs。。。。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 #define INF 0x3f3f3f3f
 5 #define Min(a, b) (a < b ? a : b)
 6 using namespace std;
 7 
 8 
 9 char map[2][15][15];
10 bool used[2][15][15];
11 int dir[][2]={1,0, -1,0, 0,1, 0,-1};
12 int n, m, t, ans, sx, sy, sz;
13 
14 void dfs (int x, int y, int z, int step)
15 {
16     if (x<0||x>n-1 || y<0||y>m-1 || step>t)
17         return;
18     if (map[z][x][y]=='P')
19     {
20         ans = Min(ans, step);
21         return;
22     }
23     for (int i=0; i<4; i++)
24     {
25         int xx = x + dir[i][0];
26         int yy = y + dir[i][1];
27         if (map[z][xx][yy]=='#')
28         {
29             z ^= 1;
30             if (map[z][xx][yy]=='#')
31                 map[z][xx][yy] = map[z^1][xx][yy] = '*';
32         }
33         if (map[z][xx][yy]=='*' || used[z][xx][yy]) continue;
34 
35         used[z][xx][yy] = true;
36         dfs (xx, yy, z, step+1);
37         used[z][xx][yy] = false;
38     }
39 }
40 
41 void MakeMap ()
42 {
43     for (int i=0; i<n; i++)
44         for (int j=0; j<m; j++)
45         {
46             scanf (" %c", map[0][i]+j);
47             if (map[0][i][j]=='S')
48                 sx = i, sy = j, sz = 0;
49         }
50     for (int i=0;i<n; i++)
51         for (int j=0; j<m; j++)
52         {
53             scanf (" %c",map[1][i]+j);
54             if (map[1][i][j]=='S')
55                 sx = i, sy = j, sz = 1;
56         }
57 }
58 
59 int main()
60 {
61     int k;
62     scanf ("%d",&k);
63     while (k--)
64     {
65         scanf ("%d%d%d",&n, &m, &t);
66         
67         MakeMap ();
68 
69         ans = INF;
70         memset (used, 0, sizeof used);
71         used[sz][sx][sy] = true;
72         dfs (sx, sy, sz, 0);
73 
74         puts (ans!=INF ? "YES" : "NO");
75 
76     }
77     return 0;
78 }

View Code

11.http://acm.hdu.edu.cn/showproblem.php?pid=1175

连连看，把点（x_{1 ，}y₁）和（X_2， y₂）连起来，不能乖2次以上的弯；

分析：若用BFS，则搜索到的（X_2， y₂）时，只能保证最少的步数到达，不能保证转弯次数小于2次、若用DFS搜索时，在搜到（X_2， y₂）时就可进行全局标记。不过会超时。

错误代码：不知错在哪里-------WA到无爱、、、、

  1 //////错误代码
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 using namespace std;
  6 #define N 1005
  7 
  8 struct Pos
  9 {
 10     int x, y;
 11     int dir, turn;
 12 }S, E;
 13 int map[N][N];
 14 bool used[N][N];
 15 int dire[][2]={1,0, -1,0, 0,1, 0,-1};
 16 int n, m;
 17 
 18 bool bfs ()
 19 {
 20     Pos Pre, Cur;
 21     queue <Pos> Q;
 22     while (!Q.empty ()) Q.pop();
 23     memset (used, 0, sizeof used);
 24 
 25     used[S.x][S.y] = true;
 26     S.turn = 0;
 27     S.dir = -1;
 28     Q.push (S);
 29     while (!Q.empty ())
 30     {
 31         Pre = Q.front ();
 32         Q.pop();
 33         for (int i=0; i<4; i++)
 34         {
 35             Cur = Pre;
 36             Cur.x += dire[i][0];
 37             Cur.y += dire[i][1];
 38             Cur.dir = i;
 39 
 40             if (Cur.dir != Pre.dir && Pre.dir!=-1)
 41                 Cur.turn++;
 42             if (Cur.x<1||Cur.x>n || Cur.y<1||Cur.y>m || Cur.turn > 2) continue;
 43 
 44             if (Cur.x==E.x && Cur.y==E.y)
 45                 return true;
 46             if (map[Cur.x][Cur.y] || used[Cur.x][Cur.y])
 47                 continue;
 48             used[Cur.x][Cur.y] = true;
 49             Q.push (Cur);
 50         }
 51     }
 52     return false;
 53 }
 54 int main ()
 55 {
 56     while (~scanf ("%d%d",&n, &m) && n+m)
 57     {
 58         for (int i=1; i<=n; i++)
 59             for (int j=1; j<=m; j++)
 60                 scanf ("%d",&map[i][j]);
 61 
 62         int t;
 63         scanf ("%d",&t);
 64         while (t--)
 65         {
 66             scanf ("%d%d%d%d",&S.x,&S.y,&E.x,&E.y);
 67 
 68             if (map[S.x][S.y] != map[E.x][E.y] || map[S.x][S.y]==0 || map[E.x][E.y]==0)
 69                 puts ("NO");
 70             else
 71                 puts (bfs ()?"YES":"NO");
 72         }
 73     }
 74     return 0;
 75 }
 76 
 77 
 78 
 79 
 80 ////AC代码；
 81 #include <cstdio>
 82 #include <cstring>
 83 #include <queue>
 84 using namespace std;
 85 #define N 1005
 86 
 87 struct Pos
 88 {
 89     int x, y;
 90     int dir, turn;
 91 }S, E;
 92 int map[N][N];
 93 bool used[N][N];
 94 int dx[]={0, 0, -1, 1};
 95 int dy[]={1, -1, 0, 0};
 96 int n, m;
 97 
 98 bool bfs ()
 99 {
100     Pos Pre, Cur;
101     queue <Pos> Q;
102     while (!Q.empty ()) Q.pop();
103     memset (used, 0, sizeof used);
104 
105     used[S.x][S.y] = true;
106     S.turn = 0;
107     S.dir = -1;
108     Q.push (S);
109     while (!Q.empty ())
110     {
111         Pre = Q.front ();
112         Q.pop();
113         for (int i=0; i<4; i++)
114         {
115             Cur = Pre;
116             Cur.x += dx[i];
117             Cur.y += dy[i];
118             Cur.dir = i;
119             if (Cur.dir != Pre.dir && Pre.dir!=-1)
120                 Cur.turn++;
121             if (Cur.x<1||Cur.x>n || Cur.y<1||Cur.y>m || Cur.turn > 2) continue;
122 
123             if (Cur.x==E.x && Cur.y==E.y)
124                 return true;
125             if (map[Cur.x][Cur.y] || used[Cur.x][Cur.y])
126                 continue;
127             used[Cur.x][Cur.y] = true;
128             Q.push (Cur);
129         }
130     }
131     return false;
132 }
133 int main ()
134 {
135 //    freopen("test.txt","r",stdin);
136     while (~scanf ("%d%d",&n, &m) && n+m)
137     {
138         for (int i=1; i<=n; i++)
139             for (int j=1; j<=m; j++)
140                 scanf ("%d",&map[i][j]);
141 
142         int t;
143         scanf ("%d",&t);
144         while (t--)
145         {
146             scanf ("%d%d%d%d",&S.x,&S.y,&E.x,&E.y);
147 
148             if (map[S.x][S.y] != map[E.x][E.y] || map[S.x][S.y]==0 || map[E.x][E.y]==0)
149                 puts ("NO");
150             else
151                 puts (bfs ()?"YES":"NO");
152         }
153     }
154     return 0;
155 }

View Code

超时代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 #define N 1005
 5 
 6 int map[N][N], turn[N][N];
 7 bool used[N][N],flag;
 8 int n, m, ex, ey;
 9 int dir[][2]={1,0, -1,0, 0,1, 0,-1};
10 
11 void dfs (int x, int y, int dire, int turn)
12 {
13     if (x<1||x>n || y<1||y>m)
14         return;
15     if (turn > 2 || flag)
16         return;
17     if (x==ex && y==ey)
18     {
19         flag = true;
20         return;
21     }
22     for (int i=0; i<4; i++)
23     {
24         int xx = x + dir[i][0];
25         int yy = y + dir[i][1];
26         if ((xx!=ex || yy!=ey) && map[xx][yy]) continue;
27         if (dire != i && dire != -1)
28             dfs (xx, yy, i, turn+1);
29         else
30             dfs (xx, yy, i, turn);
31     }
32 }
33 int main ()
34 {
35     while (~scanf ("%d%d",&n, &m) && n+m)
36     {
37         for (int i=1; i<=n; i++)
38             for (int j=1; j<=m; j++)
39                 scanf ("%d",map[i]+j);
40         int t, x, y;
41         scanf ("%d,",&t);
42         while (t--)
43         {
44             scanf ("%d%d%d%d",&x, &y, &ex, &ey);
45             if (map[x][y]!=map[ex][ey] || map[x][y]==0 || map[ex][ey]==0)
46                 puts ("NO");
47             else
48             {
49                 flag = false;
50                 dfs (x, y, -1, 0);
51                 puts (flag?"YES":"NO");
52             }
53         }
54     }
55     return 0;
56 }

View Code

12.http://acm.hdu.edu.cn/showproblem.php?pid=1010；

题意：在一个矩形的迷宫里面，问是否可以恰好在给定的时间点走到出口。

‘X'：墙壁；

’S'：起点；

‘D'：出口；

’.': 空地。

这道题，是问你是否有解，不是要求最优解，所以可以用DFS深度搜索，奇偶性剪枝+路径剪枝优化时间防TLE。如果硬是要用BFS按理来说应该是可以求出结果的，不过我BFS一直WA，一直想不通。留着以后进步了再斟酌。

DFS代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 using namespace std;
 5 
 6 int n, m, t, ex, ey;
 7 char map[10][10];
 8 bool visit[10][10], flag;
 9 int dir[][2]={1,0, -1,0, 0,1, 0,-1};
10 
11 void dfs (int x, int y, int cnt)
12 {
13     if (x<0 || x>n-1 || y<0 || y>m-1) return;
14     if (flag || cnt > t) return;
15     if (x==ex && y==ey)
16     {
17         if (cnt == t)
18             flag = true;
19         return;
20     }
21     for (int i=0; i<4; i++)
22     {
23         int xx = x + dir[i][0];
24         int yy = y + dir[i][1];
25         if (map[xx][yy]=='X' || visit[xx][yy]) continue;
26         visit[xx][yy] = true;
27         dfs (xx, yy, cnt+1);
28         if (flag) return;
29         visit[xx][yy] = false;
30     }
31 }
32 int main ()
33 {
34 //    freopen ("test.txt","r",stdin);
35     while (~scanf ("%d%d%d",&n, &m, &t) && n+m+t)
36     {
37         int wall=0, sx, sy;
38         for (int i=0; i<n; i++)
39             for (int j=0; j<m; j++)
40             {
41                 scanf (" %c",map[i]+j);
42                 if (map[i][j] == 'S')
43                 {
44                     sx = i; sy = j;
45                 }
46                 else if (map[i][j]=='D')
47                 {
48                     ex = i; ey = j;
49                 }
50                 else if (map[i][j]=='X')
51                     wall++;
52             }
53         //路径剪枝
54         if (n*m-wall < t)
55         {
56             puts ("NO");
57             continue;
58         }
59         //奇偶性剪枝
60         int tmp = fabs (sx-ex) + fabs (sy-ey);
61         if ((t - tmp) & 1)
62         {
63             puts ("NO");
64             continue;
65         }
66         memset (visit, 0, sizeof visit);
67         flag = false;
68         visit[sx][sy] = true;
69         dfs(sx, sy, 0);
70         puts ((flag?"YES":"NO"));
71     }
72     return 0;
73 }

View Code

13.http://acm.hdu.edu.cn/showproblem.php?pid=1026

题意：可怜的公主又被魔王给抓去了，被关在一个N*M的二维牢房里，并派了很多不同能力的士兵看守，一个士兵的生命值用 n 表示，表示需要 n 秒才能杀死他。问你一个勇士最少要多久才能救出公主？并输出最少时间，并打印出路线，若不能，则输出”God please help our poor hero.“；

分析：

　　求最少时间，我们可以用BFS解决，需要注意的是，遇到士兵的时候要一秒一秒的杀死，然后用时++，不能一秒杀死他，然后一次性加上他的生命值，这样就不能保证求出最优解！！

　　我们可以从终点向始点搜，然后每次保存节点前驱到一个二维数组中，然后用队列一次输出即可。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 using namespace std;
  5 #define N 105
  6 
  7 struct Pos
  8 {
  9     int x, y;
 10     int step;
 11 }path[N][N];
 12 
 13 int map[N][N], n, m;
 14 int Map[N][N], ans;
 15 bool used[N][N];
 16 int dir[][2]={1,0, -1,0, 0,1, 0,-1};
 17 
 18 bool Judge (Pos a)
 19 {
 20     if (a.x<0||a.x>n-1 || a.y<0||a.y>m-1 || used[a.x][a.y] || map[a.x][a.y]==-1)
 21         return false;
 22     return true;
 23 }
 24 
 25 int bfs ()
 26 {
 27     queue <Pos> Q;
 28     Pos Pre, Cur;
 29     while (!Q.empty ()) Q.pop();
 30 
 31     memset (used, 0, sizeof used);
 32     used[n-1][m-1] = 0;
 33 
 34     Pre.x = n-1;
 35     Pre.y = m-1;
 36     Pre.step = 0;
 37     
 38     Q.push (Pre);
 39     while (!Q.empty ())
 40     {
 41         Pre = Q.front ();
 42         Q.pop();
 43         if (Pre.x==0 && Pre.y==0)
 44             return Pre.step;
 45         if (map[Pre.x][Pre.y]>=1 && map[Pre.x][Pre.y]<=9)
 46         {
 47             Pre.step++;
 48             map[Pre.x][Pre.y]--;
 49             Q.push (Pre);
 50             continue;
 51         }
 52 
 53         for (int i=0; i<4; i++)
 54         {
 55             Cur = Pre;
 56             Cur.x += dir[i][0];
 57             Cur.y += dir[i][1];
 58             Cur.step += 1;
 59             if (Judge (Cur))
 60             {
 61                 path[Cur.x][Cur.y].x = Pre.x;
 62                 path[Cur.x][Cur.y].y = Pre.y;
 63 
 64                 used[Cur.x][Cur.y] = true;
 65                 Q.push (Cur);
 66             }
 67         }
 68     }
 69     return -1;
 70 }
 71 
 72 void PrintRoad ()
 73 {
 74     Pos Pre;
 75     queue <Pos> Q;
 76     while (!Q.empty ()) Q.pop();
 77     
 78     int x1=0, y1=0, t=1;
 79     int x2, y2;
 80     Pre.x = Pre.y = 0;
 81     Q.push(Pre);
 82     while (1)
 83     {
 84         x2 = x1;
 85         y2 = y1;
 86         Q.push (path[x2][y2]);
 87         x1 = path[x2][y2].x;
 88         y1 = path[x2][y2].y;
 89         if (x1==n-1 && y1==m-1) break;
 90     }
 91 
 92 
 93     while (!Q.empty ())
 94     {
 95         Pre = Q.front ();
 96         Q.pop();
 97         if (Map[Pre.x][Pre.y]>=1 && Map[Pre.x][Pre.y]<=10)
 98         {
 99             int guard = Map[Pre.x][Pre.y];
100             for (int i=0; i<guard; i++)
101                 printf ("%ds:FIGHT AT (%d,%d)
",t++,Pre.x,Pre.y);
102         }
103 
104         if (t==ans+1) break;
105         printf ("%ds:(%d,%d)->(%d,%d)
",t++,Pre.x,Pre.y,path[Pre.x][Pre.y].x,path[Pre.x][Pre.y].y);
106     }
107 }
108 int main()
109 {
110     char c;
111 //    freopen ("test.txt","r",stdin);
112     while (~scanf ("%d%d", &n, &m))
113     {
114         for (int i=0; i<n; i++)
115             for (int j=0; j<m; j++)
116             {
117                 scanf (" %c", &c);
118                 if (c == 'X')
119                     map[i][j] = -1;
120                 else if (c == '.')
121                     map[i][j] = 0;
122                 else if (c>='1' && c<='9')
123                     map[i][j] = c - '0';
124             }
125 
126         memcpy (Map, map, sizeof map);
127 
128         ans = bfs ();
129         if (ans == -1)
130             puts ("God please help our poor hero.");
131         else
132         {
133             printf ("It takes %d seconds to reach the target position, let me show you the way.
", ans);
134             PrintRoad ();
135         }
136         puts ("FINISH");
137     }
138     return 0;
139 }

View Code