僕は宇宙人（第2回WUPC [F]）

概要

問題文 → ■
公式解説 → なさそう？
自分の提出 → ■

解法

BFS により解きます。状態としては、

• 通過しているマス $(h,w)$
• 次に進む方向 $d$
• 次に何文字目をとろうとしているか

で、$4HWL$ 状態を考えます。 すべての $(h,w,d)$ に対して dist[(h,w,d,0)] = 0 等からの多点スタートの BFS により、$O(HWL)$ 時間で解くことができます。