ACM_82迷宫寻宝(一)

2024-05-26 02:08
文章标签 82 acm 迷宫 寻宝

本文主要是介绍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找不到宝藏。
样例输入
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++) {

这篇关于ACM_82迷宫寻宝(一)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1003257

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82, 237

总结,删除链表节点问题使用到列表,哈希表,递归比较容易超时,我觉得使用计数排序比较稳,处理起来也不是很难。 1. 力扣3217:从链表中移除在数组中的节点 1.1 题目: 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后,返回修改后的链表的头节点。 示例 1: 输入: nums = [1,2,3], head = [1,2,3,

nyoj306(走迷宫)

走迷宫 时间限制: 1000 ms  |  内存限制: 65535 KB 难度:5 描述 Dr.Kong设计的机器人卡多非常爱玩,它常常偷偷跑出实验室,在某个游乐场玩之不疲。这天卡多又跑出来了,在SJTL游乐场玩个不停,坐完碰碰车,又玩滑滑梯,这时卡多又走入一个迷宫。整个迷宫是用一个N * N的方阵给出,方阵中单元格中填充了一个整数,表示走到这个位置的难度。 这个迷宫可以向上走,向

【转载】ACM感悟

今天看了一篇我们学校前辈的ACM的感悟,觉得写的十分有道理,这里转载,文章还会不断的改进和更新。 原文链接:http://www.cnblogs.com/Chierush/p/3760870.html?ADUIN=1339764596&ADSESSION=1401536826&ADTAG=CLIENT.QQ.5329_.0&ADPUBNO=26349 声明:本文是写给弱校ACM新手的一点

我们依旧在追梦的路上-山东省第六届ACM比赛总结

这场比赛从结果而言达到了预期(金牌),从过程而言和我的预期相差甚远(打的太乱,个人发挥很差),还好关键时刻队友抗住压力,负责后果真的不堪设想。 热身赛 热身赛纯粹测机器的,先把A,B,C草草水过(A题小写x打成大写的也是醉了),我和老高开始各种测机器,long long不出所料是lld的,试了一下除0和数组越界的re问题,发现没有re,只有wa(甚至数组越界还AC了),至于栈深的话也没过多追

ACM东北地区程序设计大赛

不得不说随着参赛级别的提高,题目真的是越来越难啊,不过队长真是给力啊,在我们三个共同努力之下拿下了地区赛三等奖,哈哈我们可是大一唯一一只获奖队,终于在这次比赛打败了田大神。。。大神是失手了,俺和他差距还是挺大的。。。队友陈彤马上要去服兵役了,他说这是我们送给他最好的离别礼物,希望那家伙在部队好好干,以后谁干揍我!!!东北地区赛结束后,今年已经估计没机会参加亚洲区比赛了,赶紧补高数和线数啊!!别挂了

ACM比赛中如何加速c++的输入输出?如何使cin速度与scanf速度相当?什么是最快的输入输出方法?

在竞赛中,遇到大数据时,往往读文件成了程序运行速度的瓶颈,需要更快的读取方式。相信几乎所有的C++学习者都在cin机器缓慢的速度上栽过跟头,于是从此以后发誓不用cin读数据。还有人说Pascal的read语句的速度是C/C++中scanf比不上的,C++选手只能干着急。难道C++真的低Pascal一等吗?答案是不言而喻的。一个进阶的方法是把数据一下子读进来,然后再转化字符串,这种方法传说中

2014年ACM/ICPC亚洲区现场赛广州赛区总结

本来不想提这件事的,后来学姐找我谈心时提到这件事,我突然意识到在这件事情上我错了一次,明明答应的去参加这场比赛,最后临时决定不去......其实中间有很多很多原因 1:我和tyh,sxk临时不去主要是广州太远,我们身上money不够,呵呵。。。别笑我们,你以为我们是高富帅啊,去一趟广州消费要2个月的生活费,奖学金又没发,你让我找我妈要她辛辛苦苦挣来的工资吗?!从哈尔滨到广州单来回的火车票每个人就

《GOF设计模式》—抽象工厂(Abstract Factory)—Delphi源码示例:基于抽象工厂的迷宫

 示例:基于抽象工厂的迷宫   实现:     如果TMaze.Create是传递一个对象当作参数来建立rooms、walls及doors;如此你可以以不同的参数来改变rooms、walls及doors的类。  请注意MazeFactory也就是工厂方法(Factory Method)的一个集合;这是最通常实现抽象工厂模式的方式。同时请注意MazeFactory不是一个抽象类

走迷宫变体【拼多多1面0905】

题目大致描述: 有一个N*M的迷宫,主角被放在随机的位置上,给你一个函数,控制主角逃离迷宫。 可以使用的函数:int move(String direction) (//direction代表上下左右四个方向,分别是“U"、“D"、“L"、“R"//返回值有3种,包括-1、0、1;-1表示前面是陷阱或墙,主角不能往前走,会留在原地;0表示迷宫出口,恭喜成功逃离;1表示前面可以走,主角前进一格)