当前位置:首页 > 搜索 > 广度优先搜索 > 正文
SSOJ2487需要钥匙的迷宫
572+

题目大意:一个n*m的迷宫,路上有门,需要拿到对应的钥匙才能开门走过去,从起点到终点,至少需要走多少步?

题目描述

你所在的迷宫可以用N行M列的字符矩阵来描述:

图标 含义
# 墙,无法通过
. 地面,可以通过
小写字母 钥匙,可以打开标有对应大写字母的门
大写字母 门,可以被标有对应小写字母的钥匙打开
$ 你的初始位置
& 迷宫的出口位置

迷宫的四周都有墙,所以你无法走出这片N*M的区域,只能从“&”处离开迷宫,你只能向东西南北四个方向走。

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

输入

第1行两个正整数N和M,表示迷宫的长和宽;
第2行一个正整数P,表示门和钥匙的数量;
第3行至第N+2行,描述整个迷宫。

输出

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

样例输入

5 5 1 &A..$ ####. …#. .#.#. a#…

样例输出

28

提示

对于30%的数据点:1 <= N, M <= 15
另外存在10%的数据点:P = 0
另外存在10%的数据点:P = 1
另外存在20%的数据点:P = 2
对于所有数据点,1 <= N, M <= 50,0 <= P <= 10,保证迷宫中”$”、”&”和所有大小写字母只出现一次,钥匙和门的标号只会出现字母表中的前P个字母。

解题思路

普通迷宫的话,每个点(x,y)只有到过和没到过两种状态,或者说步数为0和不为0两种状态,现在这个迷宫多了钥匙,而且是最多10把钥匙,状态就变了,即到了(x,y)后有没有钥匙、有多少钥匙、有哪些钥匙都是要记下来的,可以用一个1024以内的二进制来表示这个钥匙的状态,即需要开至少f[50][50][1024]的数组来表示每个点的状态,然后每个点都向四个方向搜索,极限是50*50*1024*4,应该不会超时。

下面主要说一下状态转移:从一个点到另外一个点,如果是#不能走,如果是字母,状态会改变,即|对应位置的1,如果遇到小写字母,直接|,遇到大写字母,如果前面的状态没有对应的1,那么不能走。状态比较复杂,建议用结构体存储比较容易理解。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,,,,

SSOJ2487需要钥匙的迷宫:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter