1321: 营救公主
时间限制: 1 Sec 内存限制: 128 MB
提交: 156 解决: 37
[提交][状态][讨论版]
题目描述
DSKer今天又做梦了，他的睡眠质量一直很差。他梦见他化身骑士（不存在），去营救公主。
公主被困在一个迷宫里。迷宫里有N个编过号的门（N<=5)，它们分别被编号为A,B,C,D,E.为了救出公主，DSKer必须打开门，但是，开门之前必须在迷宫里找到这个打开这个门所需的所有钥匙（每个门都至少有一把钥匙），例如：现在A门有三把钥匙，DSKer就必须找全三把钥匙才能打开A门。
现在请你编写一个程序来告诉DSKer，他能不能顺利救出公主。
输入
多组测试数据。
每组测试数据的第一行包含了两个整数M,N(1<N,M<=20)，分别代表了迷宫的行和列。接下来的M每行有N个字符，描述了迷宫的布局。其中每个字符的含义如下：
.表示可以走的路
S:表示DSKer的出发点
G表示公主的位置
X表示这里有墙，DSKer无法进入或者穿过。
A,B,C,D,E表示这里是门，a,b,c,d,e表示对应大写字母的门上的钥匙。
注意DSKer只能在迷宫里向上下左右四个方向移动。
最后，输入0 0表示输入结束。
输出
每组数据输出一个YES表示DSKer能救出公主，输出NO表示他不能救出公主。
样例输入
4 4
S.X.
a.X.
..XG
....
3 4
S.Xa
.aXB
b.AG
0 0
样例输出
YES
NO
// key[] : 钥匙的总共个数
// num[] : 每次搜索能够得到的钥匙数
// isok[]: 能否得到所有的钥匙数
// 思路： 反复搜索，直到当地图无法改变（有一个大门可以解锁）或者可以到达重点
#include <bits/stdc++.h>
using namespace std;
const int N=;
char str[N][N];
bool visit[N][N];
int key[],num[];
bool isok[];
int n,m;
int s_x,s_y;
bool flag,change;
int dx[]={,,-,};
int dy[]={,-,,};
bool iskey (char c) {
if (c>='a'&&c<='e') return ;
return ;
}
bool isok1(int x,int y) {
if (x>=&&x<=n&&y>=&&y<=m&&str[x][y]!='X')
return ;
return ;
}
bool dfs (int x,int y) {
visit[x][y]=;
if (str[x][y]=='G') return ;
for (int i=;i<;i++) {
int tx=x+dx[i];
int ty=y+dy[i];
if (isok1(tx,ty)&&!visit[tx][ty]) {
if (str[tx][ty]>='A'&&str[tx][ty]<='E') {
if (isok[str[tx][ty]-'A']&&dfs(tx,ty))
return ;
}
else {
if ( iskey(str[tx][ty]) )
num[str[tx][ty]-'a']++; //小错误不要犯 （tx,ty)写成（x,y)
if (dfs(tx,ty)) return ;
}
}
}
return ;
}
int main ()
{
while (~scanf ("%d %d\n",&n,&m)&&n&&m) {
memset (isok,,sizeof(isok));
memset (key,,sizeof(key));
for (int i=;i<=n;i++) {
gets(str[i]+);
for (int j=;j<=m;j++) {
if (str[i][j]=='S') {
s_x=i;
s_y=j;
}
if (iskey(str[i][j]))
key[str[i][j]-'a']++;
}
}
flag=;
while () {
change=;
memset (visit,,sizeof(visit));
memset (num,,sizeof(num));
if (dfs(s_x,s_y)) {
flag=; break;
}
for (int i=;i<;i++) {
if (key[i]>&&key[i]==num[i])
if (!isok[i]) {
change=;
isok[i]=;
}
}
if (!change) break;
}
if (flag) puts("YES");
else puts("NO");
}
return ;
}
继续加油。。。。。做题总是会想起你。mt