Maze
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 3598 | Accepted: 1125 |
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
Source
POJ Monthly,Wang Yijie
想了好久．一开始以为和上一道状态压缩的题目相似
只有当钥匙数量达到全部以后才把钥匙加入到钥匙串．
而同一个门的所有钥匙的状态由于钥匙串的不同状态分成了不同的层，层与层之间很难转移．
然后看到讨论区中说，只有当五路可走的时候才去开门．
所以尽可能得走，如果我遇到了门，能打开就打开，打不开就再入队，不做标记．这样以后还可以访问到．
需要注意的是，对于一个打不开的门，可能反复入队造成TLE，我们可以增加一个变量记录步数，最多走m*n步．
/************************************************************************* > File Name: code/poj/2157.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: 2015年08月14日 星期五 16时02分03秒 ************************************************************************/ #include<iostream> #include<iomanip> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<string> #include<map> #include<set> #include<queue> #include<vector> #include<stack> #include <cctype> #define y0 abc111qqz #define y1 hust111qqz #define yn hez111qqz #define j1 cute111qqz #define tm crazy111qqz #define lr dying111qqz using namespace std; #define REP(i, n) for (int i=0;i<int(n);++i) typedef long long LL; typedef unsigned long long ULL; const int inf = 0x7fffffff; const int N=25; int n,m; int key[10]; bool vis[N][N]; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; char maze[N][N]; struct node { int x,y; bool ok() { if (x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&maze[x][y]!='X') return true; return false; } }; node s; void BFS() { queue<node>q; q.push(s); maze[s.x][s.y] = 'X'; int step = 0; while(!q.empty() && step < m*n) { step++; node pre; pre = q.front(); q.pop(); char ch = maze[pre.x][pre.y]; if (isupper(ch)) { if (key[ch - 'A'] == 0) { maze[pre.x][pre.y] = 'X'; } else { q.push(pre); continue; } } for (int i = 0; i < 4; i++) { node next; next . x = pre.x + dx[i]; next . y = pre.y + dy[i]; if (next.ok()) { char ch = maze[next.x][next.y]; if (ch == '.') { maze[next.x][next.y] = 'X'; q.push(next); } if (islower(ch)) { key[ch - 'a']-- ; maze[next.x][next.y] = 'X'; q.push(next); } if (ch == 'G') { printf("YES "); return; } if (isupper(ch)) { q.push(next); } } } } printf("NO "); } int main() { while (scanf("%d %d",&m,&n)!=EOF) { if (m==0&&n==0) break; memset(key,0,sizeof(key)); for ( int i = 0 ; i < m ; i++) { scanf("%s",maze[i]); } for ( int i = 0 ; i < m ; i ++) { for ( int j = 0 ; j < n ; j ++) { if (maze[i][j]=='S') { s.x = i; s.y = j; } if (islower(maze[i][j])) { key[maze[i][j]-'a']++; } } } BFS(); } return 0; }