ACM_82迷宫寻宝（一）
发布时间
阅读量：
阅读量
迷宫寻宝（一）
时间限制： 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找不到宝藏。
样例输入
样例输出
来源 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;
}
}
} 全部评论 (0)
还没有任何评论哟~