poj 2157 Maze

发表于   |  

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 3695 Accepted: 1153

Description

Acm, a treasure-explorer, is exploring again. This time he is in a special maze, in which there are some doors (at most 5 doors, represented by ‘A’, ‘B’, ‘C’, ‘D’, ‘E’ respectively). In order to find the treasure, Acm may need to open doors. However, to open a door he needs to find all the door’s keys (at least one) in the maze first. For example, if there are 3 keys of Door A, to open the door he should find all the 3 keys first (that’s three ‘a’s which denote the keys of ‘A’ in the maze). Now make a program to tell Acm whether he can find the treasure or not. Notice that Acm can only go up, down, left and right in the maze.

Input

The input consists of multiple test cases. The first line of each test case contains two integers M and N (1 < N, M < 20), which denote the size of the maze. The next M lines give the maze layout, with each line containing N characters. A character is one of the following: ‘X’ (a block of wall, which the explorer cannot enter), ‘.’ (an empty block), ‘S’ (the start point of Acm), ‘G’ (the position of treasure), ‘A’, ‘B’, ‘C’, ‘D’, ‘E’ (the doors), ‘a’, ‘b’, ‘c’, ‘d’, ‘e’ (the keys of the doors). The input is terminated with two 0’s. This test case should not be processed.

Output

For each test case, in one line output “”YES”” if Acm can find the treasure, or “”NO”” otherwise.

Sample Input

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

Sample Output

YES
NO

Sol

这题的标签是搜索。。。

哦

我写了个大暴力dfs

跪了

也许是爆栈了？

改成bfs

tle。。。

。。。

大暴力明显会tle啊！！！

这题的bfs是在每一个小房间floodfill找钥匙看看能不能进下一个小房间。。

又刷出智商下限。

日狗了 提交了这么多次还没A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
char ch[201][201];
bool bo[201][201];
int num[50],carry[50];
bool fin;
int m,n;
int X;
struct data{
	int x,y;
};
queue <data> q;
queue <data> door;
void bfs(int x,int y){
	data tmp;
	tmp.x=x;tmp.y=y;
	bo[x][y] = true;
	q.push(tmp);
	while (!q.empty()){
		while (!q.empty()){
		tmp=q.front();
		q.pop();
		x=tmp.x;
		y=tmp.y;
		// cout << ""##"" << endl;
		// cout << x << y << endl;
		// cout << tmp.carry[0] << endl;
		for (int d=0;d<4;d++){
			int nx=dir[d][0]+x;
			int ny=dir[d][1]+y;
			if (0<=nx && nx<m && 0<=ny && ny<n && ch[nx][ny]!='X' && !bo[nx][ny]){
				if (ch[nx][ny]>='A' && ch[nx][ny]<='E') {
					bo[nx][ny]=true;
					data nex;
					nex.x=nx;nex.y=ny;
					door.push(nex);
				} else {
					if (ch[nx][ny]=='G'){
						fin=true;
						return;
					} 
					bo[nx][ny]=true;
					data nex;
					nex.x=nx;nex.y=ny;
					if (ch[nx][ny]>='a' && ch[nx][ny]<='e')
						carry[ch[nx][ny]-'a']++;
					//cout << nx << "" "" << ny << endl;
					q.push(nex);
				}
			}
		} 
	}
	if (q.empty()){
			int siz=door.size();
			//cout<<siz<<endl;
			for (int i=1;i<=siz;i++){
				tmp=door.front();
				door.pop();
				//cout<<ch[tmp.x][tmp.y]<<endl;
				if (carry[ch[tmp.x][tmp.y]-'A']==num[ch[tmp.x][tmp.y]-'A'] && num[ch[tmp.x][tmp.y]-'A']!=0){
					q.push(tmp);
					//cout<<ch[tmp.x][tmp.y]<<' '<<carry[ch[tmp.x][tmp.y]-'A']<<endl;
				} else door.push(tmp);
			}
		}
	}
}

int main(){
	freopen(""1.in"",""r"",stdin);
	freopen(""1.out"",""w"",stdout);
	scanf(""%d%d"",&m,&n);
	while (m!=0 || n!=0){
		memset(ch,0,sizeof ch);
		memset(num,0,sizeof num);
		memset(carry,0,sizeof carry);
		int x,y;
		for (int i=0;i<m;i++){
			scanf(""%s"",ch[i]);
			for (int j=0;j<n;j++) {
				if (ch[i][j]=='S') x=i,y=j;
				if (ch[i][j]>='a' && ch[i][j]<='e') 
					num[ch[i][j]-'a']++;
			}
		}
		fin=false;
		memset(bo,0,sizeof bo);
		while (!door.empty()) door.pop();
		bo[x][y]=true;
		bfs(x,y);
		if (fin) puts(""YES""); else puts(""NO"");
		scanf(""%d%d"",&m,&n);
	}
}