迷宫寻宝(一)

迷宫寻宝（一）

时间限制：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
分析:bfs或dfs均可

#include <iostream>
#include <cstdio>
#include <vector> 
#include <queue>
#include <cstring>
#include <cctype>//islower

typedef struct node{
	short x,y;	
}Node;

using namespace std;

queue<Node> q;
vector<Node> door[5]; 
short sx,sy;
short m,n;
short key[5];
bool vis[20][20];
char maze[20][20];
short int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

void Input(){
	short i,j;
	for(i=0;i<m;i++) 
		for(j=0;j<n;j++){
			scanf(" %c",&maze[i][j]); 
			if(maze[i][j]=='S')
				sx=i,sy=j;
			else if(maze[i][j]>='a' && maze[i][j]<='e'){ //or islower
				key[maze[i][j]-'a']++;
			}
		}
}

bool Check(Node temp){
	if(temp.x<0 || temp.x>=m || temp.y<0 || temp.y>=n)
		return false;
	if(vis[temp.x][temp.y] || maze[temp.x][temp.y]=='X')
		return false;
	char ch=maze[temp.x][temp.y];
	if(ch>='A' && ch<='E' && key[ch-'A']){
		door[ch-'A'].push_back(temp);//对应door后添加一个Node 
		vis[temp.x][temp.y]=true;
		return false;
	}
	if(islower(ch)){
		key[ch-'a']--;
		if(!key[ch-'a'] && !door[ch-'a'].empty()){//if:最多只有一个门 
			q.push(door[ch-'a'].back());//返回最末一个结点 
			door[ch-'a'].pop_back();//移除最后一个结点 
		}
	}
	return true; 
}

void BFS(){
	short i;
	for(i=0;i<5;i++)
		door[i].clear(); //清除所有数据 
	while(!q.empty()) q.pop(); //有多组数据,而每组数据可能在找到'G'时队列不为空 
	Node now,temp;
	vis[sx][sy]=1;
	now.x=sx,now.y=sy;
	q.push(now);
	while(!q.empty()){
		now=q.front(),q.pop();
		for(i=0;i<4;i++){
			temp.x=now.x+dx[i];
			temp.y=now.y+dy[i];
			if(Check(temp)){
				if(maze[temp.x][temp.y]=='G'){
					puts("YES");return; 
				}
				vis[temp.x][temp.y]=true;
				q.push(temp);
			}
		}
	}
	puts("NO");
}

int main(){
	while(~scanf("%hd%hd",&m,&n)){
		if(!(m||n)) break;
		memset(key,0,sizeof(key));
		memset(vis,false,sizeof(vis)); 
		Input();
		BFS();
	}
	return 0;
}

其中关于Input,也可以选择下一种方式:

for(i=0;i<m;++i){
   for(j=0;j<n;++j){
	ch = getchar();
	if(ch==' ' || ch=='
'){
		--j; continue;
	}
	maze[i][j] = ch;
	if(ch>='a' && ch<='e')
		++key[ch-'a'];
	else if(ch=='S'){
		sx = i; sy = j;
	}
   }
}

关于dfs的解法,随后奉上。。。

参照:http://www.tuicool.com/articles/NF7BJv