nyoj 82-迷宫寻宝（一） (多重BFS)

82-迷宫寻宝（一）

内存限制:64MB 时间限制:1000ms 特判: No
通过数:3 提交数:5 难度:4

题目描述:

一个叫ACM的寻宝者找到了一个藏宝图，它根据藏宝图找到了一个迷宫，这是一个很特别的迷宫，迷宫里有N个编过号的门（N<=5)，它们分别被编号为A,B,C,D,E.为了找到宝藏，ACM必须打开门，但是，开门之前必须在迷宫里找到这个打开这个门所需的所有钥匙（每个门都至少有一把钥匙），例如：现在A门有三把钥匙，ACM就必须找全三把钥匙才能打开A门。现在请你编写一个程序来告诉ACM，他能不能顺利的得到宝藏。

输入描述:

输入可能会有多组测试数据（不超过10组）。
每组测试数据的第一行包含了两个整数M,N(1<N,M<20)，分别代表了迷宫的行和列。接下来的M每行有N个字符，描述了迷宫的布局。其中每个字符的含义如下：
.表示可以走的路
S:表示ACM的出发点
G表示宝藏的位置
X表示这里有墙，ACM无法进入或者穿过。
A,B,C,D,E表示这里是门，a,b,c,d,e表示对应大写字母的门上的钥匙。
注意ACM只能在迷宫里向上下左右四个方向移动。

最后，输入0 0表示输入结束。

输出描述:

每行输出一个YES表示ACM能找到宝藏，输出NO表示ACM找不到宝藏。

样例输入:

4 4 
S.X. 
a.X. 
..XG 
.... 
3 4 
S.Xa 
.aXB 
b.AG 
0 0

样例输出:

YES 
NO

分析：
　　1、要用多次BFS，每当我们找到一把钥匙我们手里的钥匙就自加，如果此时没有找到宝藏，我们依然有资本再来一次BFS，因为此时我们多了一点打开门的把握；
　　2、如果手里有的钥匙与要求开门的钥匙相同，那么这个门就可以打开，既然门打开了，如果此时我们没有找到宝藏，仍然有资本再来一次BFS
　　3、当然，BFS结束的条件是找到宝藏，或者再也找不到钥匙，再也打不开门

C/C++代码实现（AC）：

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <cmath>
  6 #include <stack>
  7 #include <map>
  8 #include <queue>
  9 #include <set>
 10 
 11 using namespace std;
 12 const int MAXN = 25;
 13 int flag, n, m, my_book[MAXN][MAXN], start_x, start_y, mov[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}, my_need[6], my_have[6];
 14 char my_map[MAXN][MAXN];
 15 struct node
 16 {
 17     int x, y;
 18 };
 19 
 20 bool my_match(node q)
 21 {
 22     if (q.x < 0 || q.y < 0 || q.x >= n || q.y >= m) return false;
 23     if (my_map[q.x][q.y] == 'X') return false;
 24     if (my_book[q.x][q.y]) return false;
 25     if (my_map[q.x][q.y] >= 'a' && my_map[q.x][q.y] <= 'e')
 26     {
 27         flag = 1;
 28         my_have[my_map[q.x][q.y] - 'a'] ++;
 29         my_map[q.x][q.y] = '.';
 30         return true;
 31     }
 32     if (my_map[q.x][q.y] >= 'A' && my_map[q.x][q.y] <= 'E')
 33     {
 34         if (my_have[my_map[q.x][q.y] - 'A'] == my_need[my_map[q.x][q.y] - 'A'])
 35         {
 36             my_map[q.x][q.y] = '.'; // 可以通过加上 flag = 1 进行优化
 37             return true;
 38         }
 39         return false;
 40     }
 41     if (my_map[q.x][q.y] == '.' || my_map[q.x][q.y] == 'G') return true;
 42 }
 43 
 44 int bfs()
 45 {
 46     flag = 0;
 47     memset(my_book, 0, sizeof(my_book));
 48     node q1, q2;
 49     queue <node> Q;
 50     q1.x = start_x, q1.y = start_y;
 51     my_book[start_x][start_y] = 1;
 52     Q.push(q1);
 53     while(!Q.empty())
 54     {
 55         q1 = Q.front();
 56         if(my_map[q1.x][q1.y] == 'G') return 1;
 57         for(int i = 0; i <= 3; ++ i)
 58         {
 59             q2 = q1;
 60             q2.x = q1.x + mov[i][0];
 61             q2.y = q1.y + mov[i][1];
 62             if (!my_match(q2)) continue;
 63             my_book[q2.x][q2.y] = 1;
 64             Q.push(q2);
 65         }
 66         Q.pop();
 67     }
 68     if (flag) return 2;
 69     return 0;
 70 }
 71 
 72 int main()
 73 {
 74     while(~scanf("%d%d", &n, &m), n || m)
 75     {
 76         memset(my_need, 0, sizeof(my_need));
 77         memset(my_have, 0, sizeof(my_have));
 78         for(int i = 0; i < n; ++ i)
 79         {
 80             getchar();
 81             scanf("%s", my_map[i]);
 82             for (int j = 0; j < m; ++ j)
 83                 if (my_map[i][j] == 'S')
 84                     start_x = i,
 85                     start_y = j;
 86                 else if (my_map[i][j] >= 'a' && my_map[i][j] <= 'e')
 87                     my_need[my_map[i][j] - 'a'] ++;
 88         }
 89 
 90         while(1)
 91         {
 92             int t = bfs();
 93             if (t == 1)
 94             {
 95                 printf("YES
");
 96                 break;
 97             }
 98             else if (t == 0)
 99             {
100                 printf("NO
");
101                 break;
102             }
103         }
104     }
105     return 0;
106 }