解説

表現の簡略化のため、板が掃く面積を単に「面積」と呼びます。

求めるものが特殊なのでどこから手を付ければ良いか分かりづらいかもしれませんが、マス $(1, 1)$ からあるマス $(i, j)$ まで行くために必要な最小の面積とマス $(i, j)$ からマス $(H, W)$ まで行くために必要な最小の面積が分かればマス $(i, j)$ を通る経路のうち最小の面積を達成するものを求められそうなので、面積を距離に見立てて最短経路問題で使用できる一般的な手法を使いたくなります。

ただし「各マスに行くために必要な最小の面積」のみを保持して更新していく方法はうまくいきません。あるマスから隣のマスへ行くことで新たに掃かれる面積はマス $1$ つ分の面積と同じ $4$ であるように思えるかもしれませんが、

実際にはその直前の移動の向きによってこの面積は変化します。方向転換が起きない場合新たに掃かれる面積は $4$ となりますが、方向転換が起きる場合には $(3 + \frac{1}{4} \pi)$ で済みます。したがって、同じ(マンハッタン)距離を進むのであればよりくねくねした動きの方が面積を小さくできます。

そこで、そのマスにどの方向から入ってきたかの情報も保持しておかないと状態の遷移が正しく行えません。よって、例えば $\mathrm{cost}[i][j][k] = ($マス$(i, j)$に $k$ の方向から入るために必要な面積$)$ などの配列を埋めていくことになります。横方向の移動は $k = 0,$ 縦方向の移動は $k = 1$ などと設定します。

面積は必ず $a + \frac{b}{4} \pi$ の形で表せることから、面積の情報はこの $(a, b)$ の組で持つとよいです。

状態の遷移は、例えば $\mathrm{cost}[i][j][0]$ の値が更新された場合 (つまり、マス $(i, j)$ に横移動で入ってくるための最小の面積が更新された場合)

• $\mathrm{cost}[i - 1][j][1] \leftarrow \min(\mathrm{self},\, \mathrm{cost}[i][j][0] + (3 + \frac{1}{4} \pi))$ とする (マス $(i, j)$ からマス $(i - 1, j)$ への移動は縦移動)
• $\mathrm{cost}[i + 1][j][1] \leftarrow \min(\mathrm{self},\, \mathrm{cost}[i][j][0] + (3 + \frac{1}{4} \pi))$ とする (マス $(i, j)$ からマス $(i + 1, j)$ への移動は縦移動)
• $\mathrm{cost}[i][j - 1][0] \leftarrow \min(\mathrm{self},\, \mathrm{cost}[i][j][0] + 4) \hspace{3.2em}$ とする (マス $(i, j)$ からマス $(i, j - 1)$ への移動は横移動)
• $\mathrm{cost}[i][j + 1][0] \leftarrow \min(\mathrm{self},\, \mathrm{cost}[i][j][0] + 4) \hspace{3.2em}$ とする (マス $(i, j)$ からマス $(i, j + 1)$ への移動は横移動)

などとすればよいです ($\mathrm{self}$ は左辺に元々入っていた値を表します)。$\mathrm{cost}[i][j][0]$ はマス $(i, j)$ に横移動で入ってくる状態を表すのでマス $(i, j - 1)$ への移動とマス $(i, j + 1)$ への移動のどちらかは引き返す移動であり更新が不要なことが分かりますが、引き返す移動によって必要な面積が減ることは無いのでわざわざ条件分岐などを用いてこれを取り除かなくても更新は起きません。

状態数は $\Theta(HW)$ なので、Dijkstra 法などを使用して探索を行うことでマス $(H, W)$ まで行くための最小の面積を求めることができます。(マスの移動によるコストの増加量が $4$ または $(3 + \frac{1}{4} \pi)$ の $2$ 通りしかないことを利用するともっと高速に解くこともできそうです。)

$3$ 次元配列 $\mathrm{cost}$ の初期値は、$\mathrm{cost}[i][j][k] = \begin{cases}\pi \hspace{0.5em} &\mathrm{for} \ (i, j) = (0, 0) \\\infty &\mathrm{otherwise}\end{cases}$ としてマス $(0, 0)$ から探索を開始してしまうと例えばマス $(0, 1)$ に横移動で入ってくるために必要な面積 $\mathrm{cost}[0][1][0]$ が $\mathrm{cost}[0][0][1] + (3 + \frac{1}{4} \pi)$ = $3 + \frac{5}{4} \pi$ として計算されてしまい(実際には存在しない「マス $(0, 0)$ へ縦移動で入ってくる」のに必要な面積 $\pi$ と、そこから方向転換を行って横移動でマス $(0, 1)$ へ入ってくる面積を計算してしまう)、実際に必要な面積よりも小さい値が求まってしまいます。

この問題に対しては、そのまま $(1 - \frac{1}{4} \pi)$ だけ小さい値で答えを求めてしまって最後に調整を行うか、マス $(0, 0)$ のみに対してだけでなく $\mathrm{cost}[0][1][0] = \mathrm{cost}[1][0][1] = 4 + \pi$ という風に隣のマスにも初期値を設定して、探索の開始点をマス $(0, 1)$ とマス $(1, 0)$ に設定するなどするとよいです。いずれの場合も $H$ や $W$ が $1$ のケースには注意してください。

解答例 (C++)