| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 799 人关注过本帖
标题:迷 宫 带 门 求 解
只看楼主 加入收藏
乾坤洞主
Rank: 3Rank: 3
来 自:乾坤洞
等 级:论坛游侠
帖 子:93
专家分:103
注 册:2012-7-18
结帖率:77.78%
收藏
已结贴  问题点数:100 回复次数:5 
迷 宫 带 门 求 解

迷 宫

【问题描述】

迷宫游戏有多种。有的迷宫只要你能走出来就算成功;有的是要求不但能走出来,而且走的步数越少得分越高。为了能得到高分,你肯定在路线的选择上下功夫,尽量用最少的步数走出迷宫。

现有一个迷宫,可以用M行N列的矩阵来描述,迷宫中有以下6种标志:

(1)$ :代表你所在的初始位置;

(2)& :迷宫的出口位置;

(3)# :墙,无法通过;


(4). :地面,可以通过;

(5)A、B、C、...、Z :每个大写字母代表一个门,可以用对应的小写字母的钥匙打开。

(6)a、b、c、...、z :每个小写字母代表一把钥匙,可以打开相应大写字母对应的门。

迷宫说明:

(1)迷宫的四周都有墙,所以你无法走出这片M*N的区域,只能从出口’&’处离开迷宫;

(2)在迷宫中你只能向东西南北四个方向走(当然有墙的地方你无法达到;如果没有相应的钥匙,有门的地方你也无法到达)。

(3)如果能走到有小写字母(钥匙)的位置,你就可以拿到它,并用来打开相应大写字母的门,钥匙a只能开A门,钥匙b只能开B门,……
如下列迷宫
图片附件: 游客没有浏览图片的权限,请 登录注册



最快走出迷宫的方法是:从初始位置$走12步到达钥匙a处拿到钥匙后,然后再走5步到达A处,打开门A后再走1步到达出口&,共走了12+5+1=18步。

上述迷宫中,如果你拿不到钥匙a,就无法打开门A,也就到不了出口。

有的迷宫可能不需要走有门的地方,就能最快走到迷宫出口。

你的任务是,计算出走出迷宫需要的最少步数是多少?

【输入格式】

第1行两个正整数M和N,表示迷宫的长和宽;

第2行一个正整数P,表示门和钥匙的数量(钥匙和门的标号只会出现字母表的前P个字母,如p=2,则只出现钥匙a,b和门A,B)。

第3行至第M+2行,描述整个迷宫。

【输出格式】

一个整数,为走出迷宫需要的最少步数或-1(如果不可能走出迷宫)。

【输入输出样例1】

maze.in
 

maze.out

5 5

1

&A..$

#.##.

...#.

.#.#.

a#...

 
 

18

 

【输入输出样例2】

maze.in
 

maze.out

1 4

1

&aA$

 
 

-1
之前 想了 很多我想分步先找钥匙 在从钥匙到门发现 一扇门还可以 多了就挂掉了!
搜索更多相关主题的帖子: 而且 游戏 钥匙 字母 
2015-09-10 14:23
乾坤洞主
Rank: 3Rank: 3
来 自:乾坤洞
等 级:论坛游侠
帖 子:93
专家分:103
注 册:2012-7-18
收藏
得分:0 
哎,B版也不在了,不然肯定有人回!

和尚我爱四处游,疯疯癫癫有理由    
开开心心是正道,愁愁烦烦不应该
2015-09-10 17:12
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:25 
这类题目有点烧脑子,有时间我弄下。我觉得还是穷举法,也不需要分两步走,捡到钥匙是可以继续前行的吧?

能编个毛线衣吗?
2015-09-10 17:47
诸葛欧阳
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:流年
等 级:贵宾
威 望:82
帖 子:2790
专家分:14619
注 册:2014-10-16
收藏
得分:25 
这个可能要枚举

一片落叶掉进了回忆的流年。
2015-09-10 18:11
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:25 
question 钥匙可以使用多次么?


[fly]存在即是合理[/fly]
2015-09-11 07:38
tlliqi
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:204
帖 子:15453
专家分:65956
注 册:2006-4-27
收藏
得分:25 
以下是引用azzbcc在2015-9-11 07:38:38的发言:

question 钥匙可以使用多次么?
应该是
2015-09-11 08:53
快速回复:迷 宫 带 门 求 解
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020562 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved