← 返回题目列表

AtCoder · maximum_2013_g

G. 国王之戒塔

中文机器翻译题面 查看原题

問題

这是一款发生在虚拟现实空间中的 MMORPG。这场游戏的目标是成为第一个获得传说中的国王戒指的人,它位于一座由 100 层石头和铁制成的塔楼的第 100 层。塔内是城镇、村庄、森林、湖泊等各种田野,塔外则是一望无际的蓝天。然而,由于它们不是有翅膀的仙女,所以它们无法穿过高墙或天空。上下两层有楼梯相连,每层只有一个上下楼梯(除第一层无下降楼梯、第100层无上升楼梯外)。这些楼梯很多都被强大的怪物把守,无法轻易接近。怪物和玩家都有等级,从 1 级开始,最多 999 级。你只能打败低于你等级的敌人,但如果你打败了与你同等级的敌人,你的等级可以提升1级。即使你打败了怪物一次,它也会被设置为如果你回到遇到它的地方,你将能够再次遇到它。每一块田地在地图上都被划分为一个个方格,即使是一个方格也代表了相当大的区域,所以走过去需要一些时间。移动到没有敌人的方格(草地、城镇、楼梯)需要1个单位时间,移动到有敌人的方格需要敌人等级+1个单位时间。在上楼梯广场中,移动到上一层的下楼梯广场需要1个单位时间,相反,在下楼梯广场中,移动到下一层的上楼梯广场需要1个单位时间。

游戏一发布我就开始玩,当我决定退出游戏时,显示了注销屏幕,但我无法退出。正当我想“哦,也许这是一个错误”时,一条公告发布给了所有玩家。公告很吓人,称除非其中一名游戏参与者到达第100层的国王之环,否则任何人都无法退出游戏。而且,如果你的生命为0或者强制退出,连接本游戏的设备会发出高能电磁波,杀死你的真身。现在,一场史无前例的死亡游戏开始了。

死亡游戏开始,参与者被分成两组。一个是在第一个城镇里设防,躲避怪物危险的人,另一个是站出来以最快的速度通关的人。其中,开始出现了贬低他人、利用他人的人。即便如此,一开始我并没有将其他人的生命减为0。不过,到了一定的时候,开始出现了以将别人的生命减为0为乐来杀人的人。如果不尽快通关游戏,可能会被一群杀人犯杀死。

他努力工作,达到了相当高的楼层。庆幸的是我没有遇到凶手。真的很好。然后,突然,一阵剧烈的震动!!! (这个游戏刚刚发布,所以可能真的有一个bug。直到我们玩到这里,在玩的时候出现了很多可疑的动作。也许是软件的一个bug导致所有参与者都死了......)震动平息了。还活着。真的很好。原来,由于最近发生了地震,你现在所在的楼层无法下去了!哦,上帝。

你的任务是在给定地图信息(例如当前位置、等级和敌人位置)的情况下找到通关游戏所需的最短时间。

入力

输入将以以下形式从标准输入给出。
T W H L
[101-T層の地図]
:
[100層の地図]
第一行是一个整数T, W, H, L。 T表示剩余层数。 W表示地图的宽度。 H表示地图的深度。 L代表远端当前电平。 1 ≦ T ≦ 10, 2 ≦ W,H ≦ 10, 1 ≦ L ≦ 999得到保证。 从第二行开始,给出了每个级别的地图。

第i图层图以以下输入格式给出。
MAPi1
:
MAPiH
第i图层图j字符串MAP上线 给出ij。 MAPij的k信和k+1文字目(k用两个字符(任意奇数)表示地图上的一个方格。其含义如下。

  • ”==” : 草原
  • ”@@” : 街
  • “01”:01级敌方怪兽
  • (中略)
  • “99”:99级敌方怪兽
  • “HC”:最后的老板
  • ”##” : 高墙
  • ”  ” : 空
  • “_-”:上楼梯
  • ”-_” : 下楼梯
  • “$$”:国王戒指的位置
  • “KR”:当前位置超出
地图ij 的字符串长度保证为2W。 最终boss保证等级为100级。 第 100 层保证存在一枚国王指环。 王环方块和当前位置方块用于移动1个单位时间,就像草原一样。

出力

在一行上打印到达国王之环所需的最短时间。如果不可能的话, 在一行上输出Impossible。

入力例

3 5 5 99
  ======  
==99======
_-####@@@@
##====@@@@
  ==-_KR  
    ==    
  ##_-==  
-_==##====
  ======  
    ==    
          
    -_    
  ==HC==  
    $$    
          

出力例

217