HDU 6111 迷宫出逃

  • 2018-09-05
  • 34
  • 0

Description:

小明又一次陷入了大魔王的迷宫,在无人机的帮忙下,小明获得了整个迷宫的草图。 不同于一般的迷宫,魔王在迷宫里安置了机关,一旦触碰,那么四个方向所在的格子,将翻转其可达性(原先可通过的格子不可通过,反之亦然,机关可以反复触发)。为了防止小明很容易地出逃,魔王在临走前把钥匙丢在了迷宫某处,只有拿到钥匙,小明才能开门在出口处离开迷宫。 万般无奈之下,小明想借助聪明的你,帮忙计算是否有机会离开这个迷宫,最少需要多少时间。(每一单位时间只能向四邻方向走一步)

Input:

第一行为 T,表示输入数据组数。 下面 T 组数据,对于每组数据: 第一行是两个数字 n, m(2 < n * m <= 64),表示迷宫的长与宽。 接下来 n 行,每行 m 个字符,‘.’表示空地可以通过,‘x’表示陷阱,‘*’表示机关,‘S’代表起点,‘E’代表出口,‘K’表示钥匙(保证存在且只有一个)。

Output:

对第 i 组数据,输出 Case #i: 然后输出一行,仅包含一个整数,表示最少多少步能够拿到钥匙并走出迷魂阵,如果不能则打出-1。

Sample Input:

5
5 7
…*x..
…x…
xEx….
*x…K.
.x*…**S
5 7
K..*x..
…x…
xEx….
*x…..
.x*…S**
5 7
..K*x..
..*x*..
xEx….
*x…..
.x*…S
5 7
..K*x..
.*xx*..
*E*….
xx…..
.x*…S
4 4
S*..
**..
…E
…K

Sample Output:

Case #1:
11
Case #2:
13
Case #3:
13
Case #4:
11
Case #5:
-1

题目链接

题目地图范围不大,很容易想到bfs(宽度优先搜索),但是因为有机关可以翻转的存在,在搜索的时候无法保存整图的地图信息(不能在原图信息上更改,会影响其它搜索情况),所以在搜索的结构体中添加一个Status无符号长整型变量(因为地图最多有64个位置所以Status\in[0,2^{64}]),Status的每一位二进制数存储一个地图位置是否翻转的信息,1为翻转,0为没有翻转,这样对照原始地图信息即可获得当前地图信息。

但是这道题如果直接搜索的话因为翻转机关的存在会陷入死循环,所以要对每一步状态判断之前是否达到过这种状态来,若达到过则不必再进行搜索,这里可以利用set容器通过结构体重载来进行去重,也可以建立一个10000大小的hash表,取每个状态坐标、翻转状态、钥匙状态之和模10000作为hash值进行去重。

AC代码:

评论

还没有任何评论,你来说两句吧