この問題は最短経路問題の一種です。

グリッドの各状態を頂点とする頂点集合を考え、状態 \(X\) から一度の操作で状態 \(Y\) を得ることができるときに \(X\) から \(Y\) に辺を張り、はじめの状態からゴミがない状態までの最短距離が本問題の答えとなります。高橋君は動かないため、グリッド上のゴミの配置により状態が決まることに注意してください。

問題となるのは頂点の数ですが、これは以下の議論により \(O(H^3W^3)\) と評価できます。

グリッドにあるゴミの配置はある整数 \(lx, rx, ly, ry, dx, dy\) を用いて以下の形式で書けるものに限る。

• はじめの状態で \(lx \leq x < rx\) かつ \(ly \leq y < ry\) であってマス \((x, y)\) にゴミがあるとき、マス \((x + dx, y + dy)\) にゴミがある
• 上の規則で与えられたマス以外にはゴミは存在しない

ここで、 \(0 \leq lx, rx \leq H\)、\(-H \leq dx \leq H\) としてよいため \(lx, rx, dx\) は \(O(H)\) であり、同様に \(ly, ry, dy\) は \(O(W)\) なので状態数は \(O(H^3W^3)\) とわかる。

各頂点の出次数は高々 \(4\) であるため、このグラフ上で BFS をすることにより時間計算量は \(O(H^3W^3)\) と評価できます。

実装の際には、最短距離を上の議論における \(lx, rx, ly, ry, dx, dy\) を key とする配列により管理すればよいです。実際に盤面を持つことでも適切な実装であれば十分高速なようです。

\(lx, rx, ly, ry, dx, dy\) からゴミの有無を判定するためには二次元累積和を用いると前計算 \(O(HW)\) 時間で \(O(1)\) 時間で判定できます。writer の実装では、愚直に \(2\) 重ループを回しても十分高速でした。

実装例