- 描述
-
一个叫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
这道题比较特殊的就是对门的处理，就是当前遇到门的时候有三种情况：
1.整张地图上都没有钥匙了。
2.已经找到该门对应的钥匙了。
3.可以找到该门对应的钥匙，但是当前的状态无法到达。
所以，需要将门的信息保存起来，等找到一个门所有的钥匙时，再把没有打开的门重新加入队列即可
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class doorposition
{
int x,y;
}
class node
{
int x,y;
public node(int x,int y) {
this.x=x;
this.y=y;
}
}
public class Main {
static doorposition doorpositions[];
static int keynumber[],startx,starty,endx,endy,line,row;
static char map[][];
static int directions[][]={{-1,0},{1,0},{0,-1},{0,1}};
public static boolean overmap(int x,int y)
{
if(x<0||x>=line||y<0||y>=row)return true;
else return false;
}
public static boolean finaljudge()
{
for(int i=0;i<5;i++)
if(keynumber[i]!=0)return false;
return true;
}
public static String bfs()
{
Queue<node>queue=new LinkedList<node>();
node first=new node(startx, starty);
queue.add(first);
while(!queue.isEmpty())
{
first=queue.remove();
//这里的finaljudge()判断条件容易忽略
if(first.x==endx&&first.y==endy&&finaljudge())
return "YES";
//如果遇到的是钥匙，则总的钥匙数减1，当钥匙数为0时，将该钥匙对应的门所在的位置设置成不可访问的状态（‘X’）
if(map[first.x][first.y]>='a'&&map[first.x][first.y]<='e'&&keynumber[map[first.x][first.y]-'a']>0)
{
keynumber[map[first.x][first.y]-'a']--;
if(keynumber[map[first.x][first.y]-'a']==0)
{
node doors=new node(doorpositions[map[first.x][first.y]-'a'].x,doorpositions[map[first.x][first.y]-'a'].y);
if(map[doors.x][doors.y]=='X')
queue.add(doors);
}
}
//当遇到门时，判断当前门对应的钥匙数，如果钥匙大于0，就说明到该门时，钥匙没有收集全，将门设置为不可访问状态
if(map[first.x][first.y]>='A'&&map[first.x][first.y]<='E')
{
if(keynumber[map[first.x][first.y]-'A']>0)
{
map[first.x][first.y]='X';
continue;
}
}
//不是钥匙和门的情况，设置为不可访问状态
map[first.x][first.y]='X';
//四个方向进行搜索
for(int i=0;i<4;i++)
{
node next=new node(first.x+directions[i][0], first.y+directions[i][1]);
if(overmap(next.x,next.y)||map[next.x][next.y]=='X')continue;
queue.add(next);
}
}
return "NO";
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
while(scanner.hasNext())
{
int i,j,k;
line=scanner.nextInt();
row=scanner.nextInt();
if(line==0&&row==0)break;
String strings[]=new String[line+4];
map=new char[line+4][row+4];
doorpositions=new doorposition[5];
keynumber=new int[5];
for(i=0;i<5;i++)
{
doorpositions[i]=new doorposition();
keynumber[i]=0;
}
for(j=0;j<line;j++)
{
strings[j]=scanner.next();
for(k=0;k<row;k++)
{
map[j][k]=strings[j].charAt(k);
if(map[j][k]=='S')
{
startx=j;
starty=k;
}
if(map[j][k]=='G')
{
endx=j;
endy=k;
}
//记录钥匙数
if(map[j][k]>='a'&&map[j][k]<='e')
{
keynumber[map[j][k]-'a']++;
}
//记录门的位置
if(map[j][k]>='A'&&map[j][k]<='E')
{
doorpositions[map[j][k]-'A'].x=j;
doorpositions[map[j][k]-'A'].y=k;
}
}
}
System.out.println(bfs());
}
}
}