0-indexed とします。

\(\mathrm{dp}[i][x * W + y] := i\) 回移動したときに \((x, y)\) にいることがあり得るか

という bool 値を持った DP を考えると、外周のマスが海であることより、 \(\mathrm{dp}[i][x * W + y]\) が true のとき、

• \(T[i] =\) L ならば \(\mathrm{dp}[i+1][x*W+y-1]\)
• \(T[i] =\) R ならば \(\mathrm{dp}[i+1][x*W+y+1]\)
• \(T[i] =\) U ならば \(\mathrm{dp}[i+1][x*W+y-W]\)
• \(T[i] =\) D ならば \(\mathrm{dp}[i+1][x*W+y+W]\)

を true にし、その後海のマスに対応する値を false にする遷移で答えを求められます。

これは bitset を用いればシフトと AND で表現できるため、結局 \(O(HWN/\mathrm{wordsize})\) で解くことができました。

実装例