G - King's Ring Tower Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題

ここは仮想現実空間で行うMMORPGの中です。 このゲームの目的は、石や鉄で構成された全100層からなる塔を舞台に 第100層にあるという伝説の王の指輪を誰よりも先に入手することです。 塔の内部には街や村、森や湖など様々なフィールドが存在し、 外部には無限の蒼穹が広がっています。もっとも、 羽の生えた妖精ではない彼方は、背の高い壁や空を移動することは出来ませんが。 上下の階層は階段によって繋がっており、上り階段および下り階段は各層1つのみ存在します (例外として、第1層には下り階段は無く、第100層に上り階段はありません)。 その階段の多くは、強力な怪物に守られており簡単には近づけません。 怪物やプレーヤーにはレベルが存在し、それぞれ1レベルに始まり、最大999レベルまで存在します。 自分のレベル以下の敵しか倒せませんが、自分と同じレベルの敵を倒すと、自分のレベルを1上げることが出来ます。 一度怪物を倒しても、遭遇した場所に戻ってくると、また遭遇できるように設定されています。 各フィールドは地図上ではそれぞれマス状に区切られており、 1マスでもかなり広い地域をあらわしているため、移動時間がそれなりに掛かります。 敵なしマス(草原、街、階段)への移動は1単位時間、敵ありマスへの移動は敵レベル+1単位時間掛かります。 上り階段マスでは1単位時間かけて1階層上の下り階段マスに移動でき、 逆に、下り階段マスでは1単位時間かけて1階層下の上り階段マスに移動できます。

リリースされて早速遊んでいた彼方はそろそろゲームをやめようと ログアウト画面を表示、、、できません。あれ、バグかな、と思っていると 全プレーヤーに聞こえるようにアナウンスが。 アナウンスでは恐るべきことにゲーム参加者の誰かが第100層にある王の指輪に 辿り着かなければ誰一人としてゲームからログアウトできないというのです。 さらに、もしライフが0になったり、強制的にログアウトしようとした場合、 このゲームに接続するためのデバイスが高出力の電磁波を放射し、現実の 肉体を死亡させるというのです。今ここに前代未聞のデスゲームが開始されたのでした。

デスゲームが開始され、参加者は大きく２つのグループに分かれました。 １つは最初の街に立てこもり怪物の危険から逃げた者達、 もう１つは一刻も早くこのゲームをクリアしようと立ち上がった者達でした。 その中で、他者を貶め、略取を働く輩も現れ始めました。それでも、 最初の内は、他者のライフを0にするようなことはありませんでした。 ところがある時を境に他者のライフを0にする、つまり殺人を楽しむような 輩が現れ始めたのです。これは一刻も早くゲームをクリアしなければ 殺人者集団に殺されてしまうかもしれません。

頑張った彼方はかなり高層階まで辿り着きました。 殺人者には幸い出くわしませんでした。本当によかった。 すると突然、大きな揺れが!!!! （このゲームはリリースされて間もないため本当にバグがあったのか、 ここに辿り着くまでのプレイ中に怪しい動きを度々起こしておりました。 もしかしたら、ソフトのバグによって行き成り参加者全員死亡するようなことは、、、。） 揺れがおさまりました。まだ生きている。本当によかった。 おやおや、今の地震の影響で現在いる階から下の階に下りられなくなっている ことが判明しました！オー、神よ。

あなたの仕事は、現在の位置、レベルおよび敵の位置などの地図情報が 与えられた時、クリアに必要な最短時間を求めることです。

入力

入力は以下の形式で標準入力から与えられる。 
T W H L
[101-T層の地図]
:
[100層の地図]
1行目には整数T, W, H, Lが与えられます。 Tは残り階層数を表します。 Wはマップの幅を表します。 Hはマップの奥行きを表します。 Lは彼方の現在レベルを表します。 1 ≦ T ≦ 10, 2 ≦ W,H ≦ 10, 1 ≦ L ≦ 999であることは保証されています。 2行目以降には各階層の地図が与えられます。

第i層の地図は次の入力形式で与えられる。 
MAPi1
:
MAPiH
第i層の地図のj行目には文字列MAPijが与えられます。 MAPijのk文字目とk+1文字目(kは任意の奇数)の2文字によって地図の1マスを表します。意味は次の通りです。

  • ”==” : 草原
  • ”@@” : 街
  • “01” : 01レベルの敵モンスター
  • （中略）
  • “99” : 99レベルの敵モンスター
  • “HC” : ラスボス
  • ”##” : 背の高い壁
  • ”  ” : 空
  • “_-” : 上り階段
  • ”-_” : 下り階段
  • “$$” : 王の指輪の位置
  • “KR” : 彼方の現在位置
MAPij の文字列長は 2W であることは保証されています。 ラスボスはレベル100 であることは保証されています。 王の指輪は第100層に必ず1つ存在することが保証されています。 王の指輪のマスおよび現在位置のマスは草原同様1単位時間移動に消費します。

出力

王の指輪に辿り着くまでに必要な最短時間を1行に出力せよ。 もし、不可能な場合、Impossibleを1行に出力せよ。

入力例

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

出力例

217

Source Name

Maximum-Cup 2013