【NOIP模拟赛】密室逃脱

2014年11月5日1,3790

即使czhou没有派出最强篮球阵容,机房篮球队还是暴虐了校篮球队。为了不打击校篮球队信心,czhou决定改变训练后的活动。近来,江大掌门的徒弟徒孙们纷纷事业有成,回到母校为机房捐钱捐物。财大气粗的机房组收回了五层六层的所有教室。Czhou决定将六层的教室改造为智能密室逃脱活动室。

每天傍晚,神牛们可以依次逐个进入游玩。我们简单的将教室分割为n*n个房间,K是你初始所在房间,T是你最终逃脱的房间。如果你想要逃脱房间,你必须依次找到m把钥匙。我们假定你从一个房间进入另一个房间需要花费1的时间。当然某些房间有些特殊的问题(地图上S表示)需要回答才能通过,对于机智的众牛们来说,这些问题根本不是问题。我们假定众牛们花费1的时间解决问题。(主要是出题的人表述不清,导致众牛理解困难;当然问题只需要回答一次,下次再次进入房间不需要y回答了)

Input:maze.in

第一行两个数字n,m

接下来n*n描述地图

Output: maze.out

需要最少步数逃脱密室。若无解输出impossible

Sample1.in:

3 1

K.S

##1

1#T

Sample1.outvb

5

Sample2.in

3 1

K#T

.S#

1#.

Sample2.out

Impossible

Sample3.in

3 2

K#T

.S.

21.

Sample3.out

8

样例3说明:

要先取钥匙1,再取钥匙2。地图上可能有多个同一种钥匙,#为墙壁即不可走.

数据范围:

0 < N <= 100, 0<=M<=9,S的个数<=5

题解

这题由于S较小,2^5枚举S的方案。。。然后直接bfs即可 即当枚举走那些S之后,原图的所有节点权都变成了1,至于按顺序取钥匙可以做分层图,f[i][j]为第i个点取到钥匙j的路径长