111qqz的小窝

老年咸鱼冲锋!

hdu 1429胜利大逃亡(续) (bfs+状态压缩)

胜利大逃亡(续)

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6652    Accepted Submission(s): 2314

Problem Description
Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……

这次魔王汲取了上次的教训,把Ignatius关在一个n*m的地牢里,并在地牢的某些地方安装了带锁的门,钥匙藏在地牢另外的某些地方。刚开始Ignatius被关在(sx,sy)的位置,离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t分钟回地牢视察一次,若发现Ignatius不在原位置便把他拎回去。经过若干次的尝试,Ignatius已画出整个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢,如果魔王回来的时候刚好走到出口或还未到出口都算逃亡失败。

 

 

Input
每组测试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的n行m列为地牢的地图,其中包括:

. 代表路
* 代表墙
@ 代表Ignatius的起始位置
^ 代表地牢的出口
A-J 代表带锁的门,对应的钥匙分别为a-j
a-j 代表钥匙,对应的门分别为A-J

每组测试数据之间有一个空行。

 

 

Output
针对每组测试数据,如果可以成功逃亡,请输出需要多少分钟才能离开,如果不能则输出-1。
 

 

Sample Input
4 5 17
@A.B.
a*.*.
*..*^
c..b*

4 5 16
@A.B.
a*.*.
*..*^
c..b*

 

 

Sample Output
16
-1
 

 

Author
LL
 

 

 

Source
 
这道题不错.
之前做过一个按照顺序找食物的,这道题和那个不一样.
并不能用一般的dfs做掉,因为可能先遇到的门的钥匙在后拓展的路径才能遇到,这样标记了的话就回不来了.
由于钥匙最多才10把,我们考虑状态压缩,一个十位二进制数表示当前拥有的”钥匙串”
当遇到一个小写字母(钥匙)的时候,把这把钥匙添加到钥匙串中.比如我现在的钥匙串是0000001010,表示我有b,d两把钥匙这个时候我遇到了f
那么我们先计算当前钥匙在钥匙串中所在的位置,构建一个只含这把钥匙的钥匙串  1<<('f'-'a') 为 0000100000,
然后通过|(逻辑或)运算,把这个钥匙串添加到之前的钥匙串中 0000001010|0000100000 = 0000101010  表示我现在有了 b,d,f三把钥匙.
对于遇到门的时候,我们要看这把门的钥匙在不在.做法是把这把门的钥匙所在的位置的状态取出来.
比如我遇到了门D,当前的钥匙串是0000101010 , 0000101010>>(D-‘A’)=0000101 ,此时最后一位就是D门的状态
0000101&1判断最后一位是否为1.
 
其他就是一个朴素的bfs
喵呜,第一次用结构体写.
还有一点需要注意的是,无法逃脱可能有两种情况,一种是因为时间不够逃脱,另一种是迷宫本身没有通路导致不能逃脱,因为这个wa了好几次
把 ans 初始设置成inf 就好.
具体见代码
 

说点什么

您将是第一位评论人!

提醒
wpDiscuz
粤ICP备18103363