迷宫寻宝(一)
时间限制:1000 ms
| 内存限制:65535 KB
难度:4
- 描述
-
一个叫ACM的寻宝者找到了一个藏宝图,它根据藏宝图找到了一个迷宫,这是一个很特别的迷宫,迷宫里有N个编过号的门(N<=5),它们分别被编号为A,B,C,D,E.为了找到宝藏,ACM必须打开门,但是,开门之前必须在迷宫里找到这个打开这个门所需的所有钥匙(每个门都至少有一把钥匙),例如:现在A门有三把钥匙,ACM就必须找全三把钥匙才能打开A门。现在请你编写一个程序来告诉ACM,他能不能顺利的得到宝藏。
-
- 输入
-
输入可能会有多组测试数据(不超过10组)。
每组测试数据的第一行包含了两个整数M,N(1<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
- 来源
-
POJ月赛改编 - 上传者
-
张云聪 - 思路:
-
不相关集
- 首先是TL掉的:
-
这个目测的是没有考虑到
可能A类门有多个, 门可能连环, 导致无限等待 - package practise;
- import
java.awt.Point; - import
java.util.ArrayList; - import
java.util.Scanner; - //TL
- public
class FindPiece { - public
static void main(String[] args) { - FindPiece findPiece = new FindPiece();
- findPiece.solution();
- }
- public
void solution() { - Scanner in = new Scanner(System.in);
- while
(true) { - int x
= in.nextInt(); - int y
= in.nextInt(); - if ((x
== 0) && (y == 0)) { - break;
- }
- if ((x
== 0) || (y == 0)) { - System.out.println("NO");
- continue;
- }
- char[][] map = new char[x + 2][y + 2];
- for
(int i = 1; i <= x; i++) { - String
buffer = in.next(); - for
(int j = 1; j <= y; j++) { - map[i][j] = buffer.charAt(j - 1);
- }
- }
- for
(int i = 0; i < x + 2; i++) { - map[i][0] = 'X';
- map[i][y + 1] = 'X';
- }
- for
(int i = 0; i < y + 2; i++) { - map[0][i] = 'X';
- map[x
+ 1][i] = 'X'; - }
- UnRelatedSet unRelatedSet = new UnRelatedSet(map, x,
y); - unRelatedSet.sort();
- if(unRelatedSet.findPiece()){
- System.out.println("YES");
- }else{
- System.out.println("NO");
- }
- }
- }
- class
UnRelatedSet { - char[][] map; // 记录地图
- char[]
doorList = { 'A', 'B', 'C', 'D', 'E' }; - char[]
keyList = { 'a', 'b', 'c', 'd', 'e' }; - int x;
// 记录地图的大小 - int
y; - ArrayList blockList; // 记录连通图
- KeyCounter keyCounter; // 记录每个门的钥匙数量
- ArrayList DoorPosition;
- ArrayList KeyAPosition;
- ArrayList KeyBPosition;
- ArrayList KeyCPosition;
- ArrayList KeyDPosition;
- ArrayList KeyEPosition;
- public
UnRelatedSet(char[][] map, int x, int y) { - this.map = map;
- this.x
= x; - this.y
= y; - blockList = new ArrayList();
- keyCounter = new KeyCounter();
- }
- private boolean isDoor(char in) {
- for
(int i = 0; i < doorList.length; i++) { - if (in
== doorList[i]) { - return
true; - }
- }
- return
false; - }
- public
void sort() { - DoorPosition = new ArrayList();
- KeyAPosition = new ArrayList();
- KeyBPosition = new ArrayList();
- KeyCPosition = new ArrayList();
- KeyDPosition = new ArrayList();
- KeyEPosition = new ArrayList();
- blockList = new ArrayList();
- keyCounter = new KeyCounter();
- for
(int i = 1; i <= x; i++) { - for
(int j = 1; j <= y; j++) { - if
(map[i][j] != 'X') { - if
(!isDoor(map[i][j])) { - Point
temp_Point = new Point(i, j); - Block
temp_Block = new Block(temp_Point); - switch
(map[i][j]) { - case
'S': - temp_Block.isSin = true;
- break;
- case
'G': - temp_Block.isGin = true;
- break;
- case
'a': - keyCounter.countA++;
- temp_Block.key_A++;
- KeyAPosition.add(new Point(i, j));
- break;
- case
'b': - keyCounter.countB++;
- temp_Block.key_B++;
- KeyBPosition.add(new Point(i, j));
- break;
- case
'c': - keyCounter.countC++;
- temp_Block.key_C++;
- KeyCPosition.add(new Point(i, j));
- break;
- case
'd': - keyCounter.countD++;
- temp_Block.key_D++;
- KeyDPosition.add(new Point(i, j));
- break;
- case
'e': - keyCounter.countE++;
- temp_Block.key_E++;
- KeyEPosition.add(new Point(i, j));
- break;
- }
- for
(int k = 0; k < blockList.size(); k++) { - Block
temp = blockList.get(k); - if
(temp.pointList - .contains(new Point(i - 1, j))
- ||
temp.pointList.contains(new Point(i, - j -
1))) { - temp_Block.add(temp);
- blockList.remove(temp);
- k--;
- continue;
- }
- }
- blockList.add(temp_Block);
- }else{
- DoorPosition.add(new Point(i,j));
- }
- }
- }
- }
- for(int i = 0 ; i< DoorPosition.size() ;
i++){ - Point
temp = DoorPosition.get(i); - for(int j = 0 ; j < blockList.size()
;j++){ - ArrayList temp_pointList =
blockList.get(j).pointList; - if((temp_pointList.contains(new
Point(temp.x-1,temp.y)))|| - (temp_pointList.contains(new
Point(temp.x+1,temp.y)))|| - (temp_pointList.contains(new
Point(temp.x,temp.y-1)))|| - (temp_pointList.contains(new
Point(temp.x,temp.y+1)))){ - if(!blockList.get(j).AccessDoor.contains(map[temp.x][temp.y])){
- blockList.get(j).AccessDoor.add(map[temp.x][temp.y]);
- }
- }
- }
- }
- }
- public
boolean findPiece(){ - Block
start_Block = new Block(new Point(-1,-1)); - for(int i = 0 ; i < blockList.size();i++){
- if(blockList.get(i).isSin){
- start_Block = blockList.get(i);
- break;
- }
- }
- if(start_Block.isGin){
- return
true; - }
- for(int j = 0 ; j <
start_Block.AccessDoor.size();j++){ - switch(start_Block.AccessDoor.get(j)){
- case
'A': - if(start_Block.key_A == keyCounter.countA){
- for(int i = 0;i <
DoorPosition.size();i++){ - if(map[DoorPosition.get(i).x][DoorPosition.get(i).y] ==
'A'){ - map[DoorPosition.get(i).x][DoorPosition.get(i).y]
='.'; - }
- }
- for(int i = 0 ; i < KeyAPosition.size() ;
i++){ - map[KeyAPosition.get(i).x][KeyAPosition.get(i).y] =
'.'; - }
- sort();
- return
findPiece(); - }
- break;
- case
'B': - if(start_Block.key_B == keyCounter.countB){
- for(int i = 0;i <
DoorPosition.size();i++){ - if(map[DoorPosition.get(i).x][DoorPosition.get(i).y] ==
'B'){ - map[DoorPosition.get(i).x][DoorPosition.get(i).y]
='.'; - }
- }
- for(int i = 0 ; i < KeyBPosition.size() ;
i++){ - map[KeyBPosition.get(i).x][KeyBPosition.get(i).y] =
'.'; - }
- sort();
- return
findPiece(); - }
- break;
- case
'C': - if(start_Block.key_C == keyCounter.countC){
- for(int i = 0;i <
DoorPosition.size();i++){ - if(map[DoorPosition.get(i).x][DoorPosition.get(i).y] ==
'C'){ - map[DoorPosition.get(i).x][DoorPosition.get(i).y]
='.'; - }
- }
- for(int i = 0 ; i < KeyCPosition.size() ;
i++){ - map[KeyCPosition.get(i).x][KeyCPosition.get(i).y] =
'.'; - }
- sort();
- return
findPiece(); - }
-
break; - case
'D': - if(start_Block.key_D == keyCounter.countD){
- for(int i = 0;i <
DoorPosition.size();i++){ - if(map[DoorPosition.get(i).x][DoorPosition.get(i).y] ==
'D'){ - map[DoorPosition.get(i).x][DoorPosition.get(i).y]
='.'; - }
- }
- for(int i = 0 ; i < KeyDPosition.size() ;
i++){ - map[KeyDPosition.get(i).x][KeyDPosition.get(i).y] =
'.'; - }
- sort();
- return
findPiece(); - }
- break;
- case
'E': - if(start_Block.key_E == keyCounter.countE){
- for(int i = 0;i <
DoorPosition.size();i++){ - if(map[DoorPosition.get(i).x][DoorPosition.get(i).y] ==
'E'){ - map[DoorPosition.get(i).x][DoorPosition.get(i).y]
='.'; - }
- }
- for(int i = 0 ; i < KeyEPosition.size() ;
i++){ - map[KeyEPosition.get(i).x][KeyEPosition.get(i).y] =
'.'; - }
- sort();
- return
findPiece(); - }
- break;
- }
- }
- return
false; - }
- }
- //
用于记录不同块的信息 - class
Block { - ArrayList pointList; // 记录节点坐标
- ArrayList AccessDoor; // 记录链接的门;
- int
key_A; - int
key_B; - int
key_C; - int
key_D; - int
key_E; - boolean isSin;
- boolean isGin;
- public
Block(Point point) { - pointList = new ArrayList();
- pointList.add(point);
- AccessDoor = new ArrayList();
- key_A
= 0; - key_B
= 0; - key_C
= 0; - key_D
= 0; - key_E
= 0; - isSin
= false; - isGin
= false; - }
- public
void add(Block block) { - pointList.addAll(block.pointList);
- key_A
+= block.key_A; - key_B
+= block.key_B; - key_C
+= block.key_C; - key_D
+= block.key_D; - key_E
+= block.key_E; - isSin
= isSin || block.isSin; - isGin
= isGin || block.isGin; - for(int i = 0 ; i < block.AccessDoor.size()
;i++){ - if(!
AccessDoor.contains(block.AccessDoor.get(i))){ - AccessDoor.add(block.AccessDoor.get(i));
- }
- }
- }
- }
- // 用于
记录每个门所需要的钥匙数量 - class
KeyCounter { - int
countA; - int
countB; - int
countC; - int
countD; - int
countE; - public
KeyCounter() { - countA
= 0; - countB
= 0; - countC
= 0; - countD
= 0; - countE
= 0; - }
- }
- }
- 然后是A掉的
这个采用了递归 效率比较低
,但是用空间换取时间且无视掉了多个门的情况,这样就毫无毫无压力了 - package practise;
- import java.awt.Point;
- import
java.util.ArrayList; - import
java.util.Scanner; - public class FindPiece_V1
{ - public static void
main(String[] args) { - FindPiece_V1 findPiece = new
FindPiece_V1(); - findPiece.solution();
- }
- public void solution()
{ - Scanner in = new
Scanner(System.in); - while (true) {
- int x = in.nextInt();
- int y = in.nextInt();
- if ((x == 0) && (y
== 0)) { - break;
- }
- if ((x == 0) || (y == 0))
{ - System.out.println("NO");
- continue;
- }
- char[][] map = new char[x +
2][y + 2]; - for (int i = 1; i <= x;
i++) { - String buffer =
in.next(); - for (int j = 1; j <= y;
j++) { - map[i][j] = buffer.charAt(j
- 1); - }
- }
- for (int i = 0; i < x +
2; i++) { - map[i][0] = 'X';
- map[i][y + 1] = 'X';
- }
- for (int i = 0; i < y +
2; i++) { - map[0][i] = 'X';
- map[x + 1][i] = 'X';
- }
- UnRelatedSet unRelatedSet =
new UnRelatedSet(map, x, y); - unRelatedSet.sort();
- if(unRelatedSet.findPiece()){
- System.out.println("YES");
- }else{
- System.out.println("NO");
- }
- }
- }
- class UnRelatedSet {
- char[][] map; // 记录地图
- char[] doorList = { 'A',
'B', 'C', 'D', 'E' }; - char[] keyList = { 'a', 'b',
'c', 'd', 'e' }; - int x; // 记录地图的大小
- int y;
- ArrayList blockList; //
记录连通图 - KeyCounter keyCounter; //
记录每个门的钥匙数量 - public UnRelatedSet(char[][]
map, int x, int y) { - this.map = map;
- this.x = x;
- this.y = y;
- blockList = new
ArrayList(); - keyCounter = new
KeyCounter(); - }
- private boolean isDoor(char
in) { - for (int i = 0; i <
doorList.length; i++) { - if (in == doorList[i])
{ - return true;
- }
- }
- return false;
- }
- public void sort() {
- ArrayList DoorPosition = new
ArrayList(); - for (int i = 1; i <= x;
i++) { - for (int j = 1; j <= y;
j++) { - if (map[i][j] != 'X') {
- if (!isDoor(map[i][j]))
{ - Point temp_Point = new
Point(i, j); - Block temp_Block = new
Block(temp_Point); - switch (map[i][j]) {
- case 'S':
- temp_Block.isSin =
true; - break;
- case 'G':
- temp_Block.isGin =
true; - break;
- case 'a':
- keyCounter.countA++;
- temp_Block.key_A++;
- break;
- case 'b':
- keyCounter.countB++;
- temp_Block.key_B++;
- break;
- case 'c':
- keyCounter.countC++;
- temp_Block.key_C++;
- break;
- case 'd':
- keyCounter.countD++;
- temp_Block.key_D++;
- break;
- case 'e':
- keyCounter.countE++;
- temp_Block.key_E++;
- break;
- }
- for (int k = 0; k <
blockList.size(); k++) { - Block temp =
blockList.get(k); - if (temp.pointList
- .contains(new Point(i - 1,
j)) - ||
temp.pointList.contains(new Point(i, - j - 1))) {
- temp_Block.add(temp);
- blockList.remove(temp);
- k--;
- continue;
- }
- }
- blockList.add(temp_Block);
- }else{
- DoorPosition.add(new
Point(i,j)); - }
- }
- }
- }
-
- for(int i = 0 ; i<
DoorPosition.size() ; i++){ - Point temp =
DoorPosition.get(i); - for(int j = 0 ; j <
blockList.size() ;j++){ - ArrayList temp_pointList =
blockList.get(j).pointList; - if((temp_pointList.contains(new Point(temp.x-1,temp.y)))||
- (temp_pointList.contains(new
Point(temp.x+1,temp.y)))|| - (temp_pointList.contains(new
Point(temp.x,temp.y-1)))|| - (temp_pointList.contains(new
Point(temp.x,temp.y+1)))){ - if(!blockList.get(j).AccessDoor.contains(map[temp.x][temp.y])){
- blockList.get(j).AccessDoor.add(map[temp.x][temp.y]);
- }
- }
- }
- }
- }
- public
boolean findPiece(){ - Block start_Block = new
Block(new Point(-1,-1)); - for(int i = 0 ; i <
blockList.size();i++){ - if(blockList.get(i).isSin){
- start_Block =
blockList.get(i); - blockList.remove(i);
- break;
- }
- }
- if(start_Block.isGin){
- return true;
- }
- ArrayList accessed = new
ArrayList(); - boolean run = true;
- while(run){
- for(int i = 0 ; i <
start_Block.AccessDoor.size();i++){ - boolean isChanged =
false; - char door =
start_Block.AccessDoor.get(i); - switch(door){
- case 'A':
- if(start_Block.key_A ==
keyCounter.countA){ - for(int j = 0 ; j <
blockList.size();j++){ - if(blockList.get(j).AccessDoor.contains('A')){
- if(blockList.get(j).isGin){
- return true;
- }
- start_Block.add(blockList.get(j));
- blockList.remove(j);
- j--;
- }
- }
- for(int k = 0 ; k <
start_Block.AccessDoor.size();k++){ - if(start_Block.AccessDoor.get(k)=='A'){
- start_Block.AccessDoor.remove(k);
- }
- }
- isChanged = true;
- }
- break;
- case 'B':
- if(start_Block.key_B ==
keyCounter.countB){ - for(int j = 0 ; j <
blockList.size();j++){ - if(blockList.get(j).AccessDoor.contains('B')){
- if(blockList.get(j).isGin){
- return true;
- }
- start_Block.add(blockList.get(j));
- blockList.remove(j);
- j--;
- }
- }
- for(int k = 0 ; k <
start_Block.AccessDoor.size();k++){ - if(start_Block.AccessDoor.get(k)=='B'){
- start_Block.AccessDoor.remove(k);
- }
- }
- isChanged = true;
- }
- break;
- case 'C':
- if(start_Block.key_C ==
keyCounter.countC){ - for(int j = 0 ; j <
blockList.size();j++){ - if(blockList.get(j).AccessDoor.contains('C')){
- if(blockList.get(j).isGin){
- return true;
- }
- start_Block.add(blockList.get(j));
- blockList.remove(j);
- j--;
- }
- }
- for(int k = 0 ; k <
start_Block.AccessDoor.size();k++){ - if(start_Block.AccessDoor.get(k)=='C'){
- start_Block.AccessDoor.remove(k);
- }
- }
- isChanged = true;
- }
- break;
- case 'D':
- if(start_Block.key_D ==
keyCounter.countD){ - for(int j = 0 ; j <
blockList.size();j++){ - if(blockList.get(j).AccessDoor.contains('D')){
- if(blockList.get(j).isGin){
- return true;
- }
- start_Block.add(blockList.get(j));
- blockList.remove(j);
- j--;
- }
- }
- for(int k = 0 ; k <
start_Block.AccessDoor.size();k++){ - if(start_Block.AccessDoor.get(k)=='D'){
- start_Block.AccessDoor.remove(k);
- }
- }
- isChanged = true;
- }
- break;
- case 'E':
- if(start_Block.key_E ==
keyCounter.countE){ - for(int j = 0 ; j <
blockList.size();j++){ - if(blockList.get(j).AccessDoor.contains('E')){
- if(blockList.get(j).isGin){
- return true;
- }
- start_Block.add(blockList.get(j));
- blockList.remove(j);
- j--;
- }
- }
- for(int k = 0 ; k <
start_Block.AccessDoor.size();k++){ - if(start_Block.AccessDoor.get(k)=='E'){
- start_Block.AccessDoor.remove(k);
- }
- }
- isChanged = true;
- }
- break;
- }
- if(isChanged){
- break;
- }else{
- if(i ==
(start_Block.AccessDoor.size()-1)){ - run = false;
- }
- }
- }
- }
- return false;
- }
- }
- // 用于记录不同块的信息
- class Block {
- ArrayList pointList; //
记录节点坐标 - ArrayList AccessDoor; //
记录链接的门; - int key_A;
- int key_B;
- int key_C;
- int key_D;
- int key_E;
- boolean isSin;
- boolean isGin;
- public Block(Point point)
{ - pointList = new
ArrayList(); - pointList.add(point);
- AccessDoor = new
ArrayList(); - key_A = 0;
- key_B = 0;
- key_C = 0;
- key_D = 0;
- key_E = 0;
- isSin = false;
- isGin = false;
- }
- public void add(Block block)
{ - pointList.addAll(block.pointList);
- key_A += block.key_A;
- key_B += block.key_B;
- key_C += block.key_C;
- key_D += block.key_D;
- key_E += block.key_E;
- isSin = isSin ||
block.isSin; - isGin = isGin ||
block.isGin; - for(int i = 0 ; i <
block.AccessDoor.size() ;i++){ - if(!
AccessDoor.contains(block.AccessDoor.get(i))){ - AccessDoor.add(block.AccessDoor.get(i));
- }
- }
- }
- }
- // 用于 记录每个门所需要的钥匙数量
- class KeyCounter {
- int countA;
- int countB;
- int countC;
- int countD;
- int countE;
- public KeyCounter() {
- countA = 0;
- countB = 0;
- countC = 0;
- countD = 0;
- countE = 0;
- }
- }
- }