No.340

グラフを構築して幅優先探索が基本方針である.

このうち, グラフ構築に時間がかかる. 愚直にやると $O(NM(W+H))$ で間に合わない.

そこで, 行/列ごとに行/列内で隣のセルに移動できるかどうかをいもす法を用いて計算する. これで計算量を $O(NM + WH)$ に抑えられる.

しかし, これでもわずかに間に合わなかったので以下の定数倍高速化でなんとか通した.

• 幅優先探索のキューとして通常使っている DList ではなく, 固定長の配列を使うキューを自作して使った. (幅優先探索なのでキューの最大長が $WH$ とわかっているため)
• 入力の読み込みに通常使っている string#to!(size_t[]) ではなく, string#splitter を使った.