搜索进阶题

1.http://acm.hdu.edu.cn/showproblem.php?pid=1254    推箱子问题

分析：由于箱子每次都只能推，而不能拉，所以我们知道，每次往方向 i 推的时候，人必然会站在一个确切的位置 p 。所以我们在每次推箱子的时候先bfs求出人是否可以到达 p 位置。若可以到达 p ，则往 p 的对面的推动一格，否则判断下一个方向。直到推到目标位置为止。然后我们得到下面的代码：

  1 //First Edit Time:    2014-11-02 17:06
  2 //Last Edit Time:    2014-11-02 18:20
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <queue>
  6 using namespace std;
  7 
  8 struct Pos
  9 {
 10     int bx, by;
 11     int px, py;
 12     int step;
 13 }Box, Person;
 14 
 15 int map[10][10], n, m;
 16 bool used[10][10][10][10];
 17 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
 18 bool visited[10][10];
 19 
 20 bool Judge_Person (Pos a)
 21 {
 22     if(a.px<0 || a.px>m-1 || a.py<0 || a.py>n-1 || visited[a.px][a.py]
 23             || map[a.px][a.py]==1 || (a.px==Box.bx && a.py==Box.by))
 24         return false;
 25     return true;
 26 }
 27 
 28 bool Judge_Box (Pos a)
 29 {
 30     if(a.bx<0 || a.bx>m-1 || a.by<0 || a.by>n-1 || used[a.bx][a.by][Person.px][Person.py] || map[a.bx][a.by]==1)
 31         return false;
 32     return true;
 33 }
 34 
 35 Pos Find_p (Pos a, int i)
 36 {
 37     Pos P = a;
 38     if (i==0)
 39     {
 40         P.px = a.bx + dir[1][0];
 41         P.py = a.by + dir[1][1];
 42     }
 43     else if (i==1)
 44     {
 45         P.px = a.bx + dir[0][0];
 46         P.py = a.by + dir[0][1];
 47     }
 48     else if (i==2)
 49     {
 50         P.px = a.bx + dir[3][0];
 51         P.py = a.by + dir[3][1];
 52     }
 53     else if (i==3)
 54     {
 55         P.px = a.bx + dir[2][0];
 56         P.py = a.by + dir[2][1];
 57     }
 58     return P;
 59 }
 60 
 61 //
 62 bool bfs_person (Pos a)
 63 {
 64     memset (visited, 0, sizeof visited);
 65     if (!Judge_Person (a)) return false;
 66 
 67     Pos Pre, Cur;
 68     queue <Pos> Q;
 69     visited[Person.px][Person.py] = true;
 70 
 71     Q.push (Person);
 72     while (!Q.empty())
 73     {
 74         Pre = Q.front();
 75         Q.pop();
 76         for (int i=0; i<4; i++)
 77         {
 78             Cur.px = Pre.px + dir[i][0];
 79             Cur.py = Pre.py + dir[i][1];
 80             if (Judge_Person (Cur))
 81             {
 82                 visited[Cur.px][Cur.py] = true;
 83                 if (Cur.px==a.px && Cur.py==a.py)
 84                     return true;
 85                 Q.push (Cur);
 86             }
 87         }
 88     }
 89     return false;
 90 }
 91 
 92 int bfs_box ()
 93 {
 94     Pos Pre, Cur, P;
 95     queue <Pos> Q;
 96     memset (used, 0, sizeof used);
 97 
 98     used[Box.bx][Box.by][Person.px][Person.py] = true;
 99     Q.push (Box);
100     while (!Q.empty ())
101     {
102         Pre = Q.front ();
103         Q.pop();
104         for (int i=0; i<4; i++)
105         {
106             Box = Pre;
107 
108             //找到推箱子的位置
109             P = Find_p (Pre, i);
110             
111             if (bfs_person (P))
112             {
113                 Cur = Pre;
114                 Person = P;
115                 Cur.bx += dir[i][0];
116                 Cur.by += dir[i][1];
117                 Cur.step += 1;
118                 if (Judge_Box (Cur))
119                 {
120                     used[Cur.bx][Cur.by][Person.px][Person.py] = true;
121                     if (map[Cur.bx][Cur.by]==3)
122                         return Cur.step;
123                     Q.push (Cur);
124                 }
125             }
126         }
127     }
128     return -1;
129 }
130 
131 int main ()
132 {
133     int t;
134     freopen ("test.in","r",stdin);
135     scanf ("%d",&t);
136     while (t--)
137     {
138         scanf ("%d%d",&m, &n);
139         for (int i=0; i<m; i++)
140             for (int j=0; j<n; j++)
141             {
142                 scanf ("%d",map[i]+j);
143                 if (map[i][j]==2)
144                     Box.bx=i, Box.by=j, Box.step=0;
145                 else if (map[i][j]==4)
146                     Person.px = i,Person.py = j;
147             }
148         int ans = bfs_box ();
149         printf ("%d
",ans);
150     }
151     return 0;
152 }
View Code

　　然后我就这样一直WA到死。后来问了学长才知道，其实我没有考虑到另一种情况：

1
5 3
0 0 0
0 0 0
0 2 0
1 4 1
1 3 1

在上面这种情况下，以上代码得到的答案是-1，因为上面的程序一开始就访问了他本应该去的位置 p ，导致最后要用到 p 的时候得到 p 不可到达的错误信息而是答案出错。

改正之后的代码：

  1 //First Edit Time:    2014-11-02 17:06
  2 //Last Edit Time:    2014-11-02 18:20
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <queue>
  6 using namespace std;
  7 
  8 struct Pos
  9 {
 10     int bx, by;
 11     int px, py;
 12     int step;
 13 }Box, Person;
 14 
 15 int map[10][10], n, m;
 16 bool used[10][10][10][10];
 17 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
 18 bool visited[10][10];
 19 
 20 bool Judge_Person (Pos a)
 21 {
 22     if(a.px<0 || a.px>m-1 || a.py<0 || a.py>n-1 || visited[a.px][a.py]
 23             || map[a.px][a.py]==1 || (a.px==Box.bx && a.py==Box.by))
 24         return false;
 25     return true;
 26 }
 27 
 28 bool Judge_Box (Pos a)
 29 {
 30     if(a.bx<0 || a.bx>m-1 || a.by<0 || a.by>n-1 || used[a.bx][a.by][Person.px][Person.py] || map[a.bx][a.by]==1)
 31         return false;
 32     return true;
 33 }
 34 
 35 Pos Find_p (Pos a, int i)
 36 {
 37     Pos P = a;
 38     if (i==0)
 39     {
 40         P.px = a.bx + dir[1][0];
 41         P.py = a.by + dir[1][1];
 42     }
 43     else if (i==1)
 44     {
 45         P.px = a.bx + dir[0][0];
 46         P.py = a.by + dir[0][1];
 47     }
 48     else if (i==2)
 49     {
 50         P.px = a.bx + dir[3][0];
 51         P.py = a.by + dir[3][1];
 52     }
 53     else if (i==3)
 54     {
 55         P.px = a.bx + dir[2][0];
 56         P.py = a.by + dir[2][1];
 57     }
 58     return P;
 59 }
 60 
 61 //
 62 bool bfs_person (Pos a)
 63 {
 64     memset (visited, 0, sizeof visited);
 65     if (!Judge_Person (a)) return false;
 66     if (a.px==Person.px && a.py==Person.py)  //改正之处。就是把那种情况特判了一下；
 67         return true;
 68     Pos Pre, Cur;
 69     queue <Pos> Q;
 70     visited[Person.px][Person.py] = true;
 71 
 72     Q.push (Person);
 73     while (!Q.empty())
 74     {
 75         Pre = Q.front();
 76         Q.pop();
 77         for (int i=0; i<4; i++)
 78         {
 79             Cur.px = Pre.px + dir[i][0];
 80             Cur.py = Pre.py + dir[i][1];
 81             if (Judge_Person (Cur))
 82             {
 83                 visited[Cur.px][Cur.py] = true;
 84                 if (Cur.px==a.px && Cur.py==a.py)
 85                     return true;
 86                 Q.push (Cur);
 87             }
 88         }
 89     }
 90     return false;
 91 }
 92 
 93 int bfs_box ()
 94 {
 95     Pos Pre, Cur, P;
 96     queue <Pos> Q;
 97     memset (used, 0, sizeof used);
 98 
 99     used[Box.bx][Box.by][Person.px][Person.py] = true;
100     Q.push (Box);
101     while (!Q.empty ())
102     {
103         Pre = Q.front ();
104         Q.pop();
105     //  printf ("Box:(%d, %d) ---- %d
",Pre.bx+1, Pre.by+1, Pre.step);
106         for (int i=0; i<4; i++)
107         {
108             Box = Pre;
109 
110             //找到推箱子的位置
111             P = Find_p (Pre, i);
112         //    printf ("Person:(%d,%d)
",P.px+1,P.py+1);
113             if (bfs_person (P))
114             {
115                 Cur = Pre;
116                 Person = P;
117                 Cur.bx += dir[i][0];
118                 Cur.by += dir[i][1];
119                 Cur.step += 1;
120     //        printf ("Goto:(%d, %d)
",Cur.bx+1, Cur.by+1);
121                 if (Judge_Box (Cur))
122                 {
123                     used[Cur.bx][Cur.by][Person.px][Person.py] = true;
124                     if (map[Cur.bx][Cur.by]==3)
125                         return Cur.step;
126                     Q.push (Cur);
127                 }
128             }
129         }
130     }
131     return -1;
132 }
133 
134 int main ()
135 {
136     int t;
137     freopen ("test.in","r",stdin);
138     scanf ("%d",&t);
139     while (t--)
140     {
141         scanf ("%d%d",&m, &n);
142         for (int i=0; i<m; i++)
143             for (int j=0; j<n; j++)
144             {
145                 scanf ("%d",map[i]+j);
146                 if (map[i][j]==2)
147                     Box.bx=i, Box.by=j, Box.step=0;
148                 else if (map[i][j]==4)
149                     Person.px = i,Person.py = j;
150             }
151         int ans = bfs_box ();
152         printf ("%d
",ans);
153     }
154     return 0;
155 }
View Code

2.http://acm.hdu.edu.cn/showproblem.php?pid=2553       N皇后问题

分析：先明确这是求所有解的问题，所有可以用DFS解答。在N*N的矩阵中，放N个皇后，由于皇后不能在同一行同一列同一斜线，所以，我们单从行来看，在一行中不可能出现两个及以上的皇后。又由于必须得放N个皇后，所以每一行都必有且仅有一个皇后。那么问题的解就可以用一个N元向量 Xi  （i=1,2,3....N）来表示。我们把N个皇后从0--N编号。C[i]表示第 i 行放置的皇后的编号。然后对数轴0--N DFS一遍即可得到答案。为防TLE，先预处理一下。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 using namespace std;
 5 
 6 int C[11], out[11], ans, n;
 7 
 8 void dfs (int cur)
 9 {
10     if (cur==n)
11     {
12         ans++;
13         return;
14     }
15     for (int i=0; i<n; i++)
16     {
17         bool ok = true;
18         C[cur] = i;
19         for (int j=0; j<cur; j++)
20             if (C[cur]==C[j] || cur-j==C[cur]-C[j] || cur+C[cur]==C[j]+j)
21             {
22                 ok = false;break;
23             }
24         if (ok)
25             dfs (cur+1);
26     }
27 }
28 
29 int main ()
30 {
31     for (int i=1; i<=10; i++)
32     {
33         ans = 0;
34         n = i;
35         dfs (0);
36         out[i] = ans;
37     }
38     while (~scanf ("%d",&n) && n)
39         printf ("%d
",out[n]);
40     return 0;
41 }
View Code

3.http://acm.hdu.edu.cn/showproblem.php?pid=2612

题意：Y和M是好朋友，他们两个打算在任一家KFC餐厅（至少有一家kFC餐厅）会面，问你，他们两个总共最少要花费多久时间才能见面？也就是他们两个各自到达这家见面餐厅的时间之和最少是多少？

分析：显然是求最优解无疑，我们首先应该可以确定用BFS求解相比DFS要好点。那么我们可能会想到在输入的时候每次标记出KFC的位子，然后一重循环，分别bfs出Y,M到到第 i 个KFC的时间，每次更新最短时间。但是这种在KFC很多的情况下，复杂度可能会很高而导致TLE。事实上，我们可以用两次BFS求出答案。首先，我们BFS出 Y 到所有KFC的时间，并记录下来。然后，我们再BFS 出 M 到所有kFC的时间，并且在到达KFC时，判断当前 M 的时间加上第一次 BFS Y 到达这个店的时间与最小值的大小关系，选出最小的即可：

代码如下：

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

4.http://acm.hdu.edu.cn/showproblem.php?pid=1495   非常可乐

分析：首先BFS求最优解，因为三个杯子之间相互倒水共六种情况：s->n, s->m, n->m, n->s, m->s, m->n;然后遍历六种情况即可，值得注意的是，一个 -= 被我写成+=，WA了N多次。

  1 //First Edit Time:    2014-11-05 20:54
  2 //Last Edit Time:    2014-11-05 20:55
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <queue>
  6 #define N 110
  7 using namespace std;
  8 
  9 struct Node
 10 {
 11     int x, y;
 12     int cup, step;
 13 };
 14 int s, n, m;
 15 bool used[N][N][N];
 16 
 17 void Move (Node &a, int i)
 18 {
 19     // 倒出的水取决于 Min（当前杯中剩余容量， 最多能倒出的水量）
 20     if (i==0)  //s -> x
 21     {
 22         int tmp = (n-a.x) < a.cup ? (n-a.x):a.cup;
 23         a.x += tmp;
 24         a.cup -= tmp;
 25     }
 26     else if (i==1) // s -> y
 27     {
 28         int tmp = (m-a.y) < a.cup ? (m-a.y):a.cup;
 29         a.y += tmp;
 30         a.cup -= tmp;
 31     }
 32     else if (i==2) // x -> s
 33     {
 34         int tmp =  (s-a.cup) < a.x ? (s-a.cup):a.x;
 35         a.cup += tmp;
 36         a.x -= tmp;
 37     }
 38     else if (i==3)  // y -> s
 39     {
 40         int tmp = (s-a.cup) < a.y ? (s-a.cup):a.y;
 41         a.cup += tmp;
 42         a.y -= tmp;
 43     }
 44     else if (i==4) // y -> x
 45     {
 46         int tmp = (n-a.x) < a.y ? (n-a.x) : a.y;
 47         a.x += tmp;
 48         a.y -= tmp;
 49     }
 50     else if (i==5)  // x -> y
 51     {
 52         int tmp = (m-a.y) < a.x ? (m-a.y) : a.x;
 53         a.y +=  tmp;
 54         a.x -= tmp;         //   -= 被写成 += wa无数，我也是醉了、
 55     }
 56 }
 57 
 58 int bfs ()
 59 {
 60     Node Pre, Cur;
 61     queue <Node> Q;
 62     memset (used, 0, sizeof used);
 63 
 64     used[s][0][0] = true;
 65     Pre.x=Pre.y=Pre.step = 0;
 66     Pre.cup = s;
 67     Q.push (Pre);
 68     while (!Q.empty())
 69     {
 70         Pre = Q.front();
 71         Q.pop();
 72      // printf ("(%d, %d, %d) ----- %d
",Pre.cup, Pre.x, Pre.y, Pre.step);
 73         if ((Pre.x==Pre.y && Pre.x+Pre.y==s)||(Pre.x==Pre.cup && Pre.x+Pre.cup==s) || (Pre.cup==Pre.y && Pre.cup+Pre.y==s))
 74             return Pre.step;
 75         for (int i=0; i<6; i++)
 76         {
 77             Cur = Pre;
 78             Move (Cur, i);
 79             Cur.step += 1;
 80     //    printf ("(%d, %d, %d)
",Cur.cup, Cur.x, Cur.y);
 81             if (!used[Cur.cup][Cur.x][Cur.y])
 82             {
 83                 used[Cur.cup][Cur.x][Cur.y] = true;
 84                 Q.push (Cur);
 85             }
 86         }
 87     }
 88     return -1;
 89 }
 90 int main ()
 91 {
 92     while (~scanf ("%d%d%d",&s, &n, &m) && s+n+m)
 93     {
 94       int ans;
 95       if (s&1) ans = -1;else ans = bfs ();
 96 
 97         if (ans == -1)
 98             puts ("NO");
 99         else
100             printf("%d
",ans);
101     }
102     return 0;
103 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/khan724/p/4069932.html