POJ 2157 Maze
2024-08-29 08:07:19
Maze
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 3183 | Accepted: 996 |
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
#include<stdio.h>
#include<iostream>
#include <string.h>
#include <queue>
using namespace std;
typedef struct node
{
int x;
int y;
node(int a, int b)
{
x = a;
y = b;
}
node()
{ }
}Map; char Maze[][];
int Dir[][] = {-,,,,,-,,};
int key[]; void BFS(int sx, int sy, int m, int n)
{
queue<Map> Queue;
Queue.push(Map(sx, sy));
Map temp;
Maze[sx][sy] = 'X';
int Limit = ;
while(!Queue.empty() && Limit < )
{
++Limit;
temp = Queue.front();
Queue.pop();
if (Maze[temp.x][temp.y] >= 'A' && Maze[temp.x][temp.y] <= 'E')
{
if (key[Maze[temp.x][temp.y] - 'A'] == )
{
Maze[temp.x][temp.y] = 'X';
}
else
{
Queue.push(temp);
continue;
}
}
for (int i = ; i < ; i++)
{
int x = temp.x + Dir[i][];
int y = temp.y + Dir[i][];
if (x >= && x < m && y >= && y < n && Maze[x][y] != 'X')
{
if (Maze[x][y] == '.')
{
Maze[x][y] = 'X';
Queue.push(Map(x, y));
}
if (Maze[x][y] >= 'a' && Maze[x][y] <= 'e')
{
key[Maze[x][y] - 'a']--;
Maze[x][y] = 'X';
Queue.push(Map(x, y));
}
if (Maze[x][y] == 'G')
{
printf("YES\n");
return;
}
if (Maze[x][y] >= 'A' && Maze[x][y] <= 'E')
{
Queue.push(Map(x, y));
}
}
}
}
printf("NO\n");
} int main()
{
int m, n;
int sx, sy;
while(scanf("%d%d", &m, &n) != EOF)
{
if (m == && n == )
{
break;
}
memset(key, , sizeof(key));
for (int i = ; i < m; i++)
{
scanf("%s", Maze[i]);
for (int j = ; j < n; j++)
{
if (Maze[i][j] == 'S')
{
sx = i;
sy = j;
}
else
{
if (Maze[i][j] >= 'a' && Maze[i][j] <= 'e')
{
key[Maze[i][j] - 'a']++;
}
}
}
}
BFS(sx, sy, m, n);
}
return ;
}
最新文章
- GitHub实战系列~2.把本地项目提交到github中 2015-12-10
- 集合和String
- MySQL5.0+提示字段没有默认值(doesn’t have a default value)的解决方法
- JNI开发中String转换chat*工具
- hdu 5877/ 2016 ACM/ICPC Dalian Online 1010 Weak Pair
- linux-kernel 学习计划
- ionic安装拍照选照片插件
- 计算UILabel的高度
- 团队作业6——展示博客(Alpha)
- android studio集成ijkplayer
- application19事件 20多少步骤 具体20多少只有微软知道!!!
- 解决chrome安装谷歌访问助手错误问题
- 010_vim和python整合开发
- Python OpenCV人脸识别案例
- LyX使用中的一些问题
- Ex 6_9 某个字符串处理语言提供了一个将字符串一分为二的基本操作..._第六次作业
- linux达人养成计划学习笔记(八)—— shell基础
- hdu 4135 [a,b]中n互质数个数+容斥
- HDU 2015 偶数求和
- I2C三态门Verilog