迷宮尋寶（一）
時間限制：1000 ms | 記憶體限制：65535 KB
難度：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
好題。做了兩天才過。。
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using std::vector;
using std::queue;
struct Node{
int x, y;
} start;
queue<Node> Q;
vector<Node> door[5];
int m, n, tkey[5], key[5], vis[22][22];
char map[22][22];
const int mov[][2] = {0, 1, 0, -1, -1, 0, 1, 0};
bool checkOpenDoor(char ch){
return key[ch - \'A\'] == tkey[ch - \'A\'];
}
//check函數的作用：1、推斷點是否越界 2、推斷是否已經訪問或為牆壁
//3、是否為鑰匙，若是則更新鑰匙且推斷是否能打開門。如能則将之前入棧
//的門入隊 4、推斷是否為門。若是再推斷是否能打開，若不能則入棧且傳回0
bool check(Node t){
if(t.x < 0 || t.y < 0 || t.x >= m || t.y >= n)
return 0;
if(vis[t.x][t.y] || map[t.x][t.y] == \'X\')
return 0;
char ch = map[t.x][t.y];
if(ch >= \'a\' && ch <= \'e\'){
++key[ch - \'a\'];
while(key[ch - \'a\'] == tkey[ch - \'a\'] && !door[ch - \'a\'].empty()){
Q.push(door[ch - \'a\'].back());
door[ch - \'a\'].pop_back();
}
}
if(ch >= \'A\' && ch <= \'E\' && !checkOpenDoor(ch)){
door[ch - \'A\'].push_back(t);
vis[t.x][t.y] = 1;
return 0;
}
return 1;
}
void BFS(){
for(int i = 0; i < 5; ++i)
door[i].clear();
while(!Q.empty()) Q.pop();
vis[start.x][start.y] = 1;
Q.push(start);
Node temp, now;
while(!Q.empty()){
now = Q.front(); Q.pop();
for(int i = 0; i < 4; ++i){
temp = now;
temp.x += mov[i][0];
temp.y += mov[i][1];
if(check(temp)){
if(map[temp.x][temp.y] == \'G\'){
puts("YES"); return;
}
vis[temp.x][temp.y] = 1;
Q.push(temp);
}
}
}
puts("NO");
}
int main(){
char ch;
while(scanf("%d%d", &m, &n), m || n){
memset(tkey, 0, sizeof(tkey));
memset(key, 0, sizeof(key));
memset(vis, 0, sizeof(vis));
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
ch = getchar();
if(ch == \' \' || ch == \'\n\'){
--j; continue;
}
map[i][j] = ch;
if(ch >= \'a\' && ch <= \'e\')
++tkey[ch - \'a\'];
else if(ch == \'S\'){
start.x = i; start.y = j;
}
}
}
BFS();
}
return 0;
} 