魔王の城への移動

問題概要

最後の冒険の終盤に差し掛かり、残るは魔王の城への突入のみとなった。

魔王の城は「最後の森」と呼ばれる場所に位置している。最後の森は$R$行$C$列のマス目で構成されており、各マスは以下のいずれかの状態を有する。

• 平地: 自由に通行可能なマス。
• 木: 通行不可能なマス。
• 強敵のいるマス: 凶暴な強敵がいるマス。一定の条件を満たさなければ通行できない。
• プレイヤーの村: プレイヤーの初期位置となるマス。自由に通行可能。
• ほこら: 伝説の剣「Link-Cut Sword」がある場所。自由に通行可能。
• 魔王の城: 魔王の城があるマス。自由に通行可能。

村、ほこら、魔王の城のマスはそれぞれ1つずつ存在する。

また、マス$(i,j)$ $(1 \leq i \leq R, 1 \leq j \leq C)$を座標$(i,j)$と呼ぶことにする。2つの異なるマス$(i,j)$と$(k,l)$が隣接するとは、以下の条件を満たす場合を指す。

• $i = k$ かつ $|j-l| = 1$。
• $j = l$ かつ $|i-k| = 1$。

プレイヤーは最初村のマスにいる。プレイヤーは以下の行動を行うことができる。

• プレイヤーの現在位置から隣接するマスに移動する。ただし、移動先のマスは通行可能なマスでなければならない。
• プレイヤーの現在位置から隣接するマスにいる強敵と戦闘を行う。戦闘に勝利すると、そのマスは通行可能となる。

魔王との戦いでは高度なプログラミングスキルが要求されるだろう。魔王に対抗するためには、手持ちの装備（ライブラリ）を強化しなければならない。特に、ほこらにある伝説の剣を入手しなければ魔王に勝つことはできないだろう。そのため、伝説の剣を入手した後でないと魔王の城に突入することはできない。ただし、伝説の剣を入手していない状態で魔王の城への通行は許可される。

さらに、最後の森には魔王が発する猛毒の霧が立ち込めているため、移動にかかる時間をできるだけ短くしなければならない。これがまさに難題のゲームだ。そこで、上記の条件を満たす移動