BFS (幅優先探索) の知識があることを前提とします。BFS については drken さんの記事 などに解説されています。グリッド上の BFS の一番基本形は ABC007 - C で練習できます。

まず考察として、薬は使うとなくなりますが、これについて考える必要はありません。この問題においては、薬を何度でも使えるとしても、 \(2\) 回以上使うことがあれば最後に使った後の行動を代わりに初めて使った後にすればよいからです。

解法 1

ある薬を使った時点で、その時点での位置、エネルギーは一意です。そのため、 \(N\) 頂点の有向グラフであって、 \(i\) から \(j\) に辺がある \(\iff\) 薬 \(i\) を使った後他の薬を使わずに薬 \(j\) の位置にたどり着ける であるようなグラフを構築して、その上で BFS をすることでこの問題を解くことができます。

薬 \(i\) を使った後他の薬を使わずに薬 \(j\) の位置にたどり着けるか？という問題は、グリッド上で薬 \(i\) の位置から BFS で最短距離を求めればよいです。\(N\) 個の薬についてその位置からグリッド上で BFS を行うので、計算量は \(O(HWN)\) です。( \(N \leq HW\) よりこれがボトルネックとなります)

実装においては、ゴール地点に薬がない場合、薬 \(N+1\) をゴール地点に作ると簡潔です。

実装例 (C++)

解法 2

(今回は最終的な解法とは若干ずれますが、典型的な考察として) 頂点倍加という方法もあります。

\((i, j, k) : \) マス \((i, j)\) にいてエネルギーが \(k\) である、という状態をグラフの \(1\) つの頂点とみなします。その上で、以下のような辺を貼ります。

• すべての \((i, j, k) \ (k \geq 1)\) について、それぞれ辺を貼る先が空きマスであるならば \((i + 1, j, k - 1), (i, j + 1, k - 1), (i - 1, j, k - 1), (i, j - 1, k - 1)\) へ辺を貼る。
• 各薬 \(i \ (1 \leq i \leq N)\) とすべての \(k\) について、 \((R_i, C_i, k)\) から \((R_i, C_i, E_i)\) へ辺を貼る。

このグラフ上で BFS を行い到達判定をすることでこの問題を解くことができますが、計算量が最悪 \(\Theta((HW)^2)\) かかります。

計算量を減らすポイントは、薬が \(N \leq 300\) 個しかないことです。各薬を使ってから他のマスに向かうのは最短路しか考慮しなくてよいので、各マスにつきエネルギーとして高々 \(N\) 個の値のみしか考慮しないでよいです。明示的に頂点を倍加させたグラフで BFS をしなくても、実装例のように \(d_{i, j} := (i, j)\) に到達したときの最大エネルギー などとした二次元配列を管理すればこの考察から計算量が \(O(HWN)\) になります。

実装例 (C++)

実際に計算量が減っている証明はできていませんが、用意できたテストケースにおいては優先度付きキューを用いる解法が非常に高速に動作します。実装例 (C++)