Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 232 D 問題 Weak Takahashi

AtCoder ABC ABC232 D問題 400 pts

問題

提出解答

問題の概要

縦 $H$ 行, 横 $W$ 列の $HW$ マスからなるグリッドがある. 各マスは空きマスか, 壁である. 空きマス $(i,j)$ にいるとき, $(i+1,j), (i,j+1)$ のうち, 空きマスが存在するならば, その空きマスから1つ選んで移動できる (場外禁止).

空きマス $(1,1)$ から移動するとき, 最大何マス通るか?

制約

$1 \leq H,W \leq 100$
$(1,1)$ は空きマス

解法

動的計画法で解く. ${\rm DP}[i,j]$ でマス $(i,j)$ から始めたときに通る最大のマスの数とする. そして, $S_{i,j}$ で, マス $(i,j)$ から移動できるマスの集合とする. このとき,

${\rm DP}[i,j]=\begin{cases} 0 & ((i,j) {\text が壁マス}) \\ 1 & ((i,j) {\text が空きマス}, S_{i,j}=\emptyset ) \\ \displaystyle \max_{(k,l) \in S_{i,j}} {\rm DP}[k,l]+1 & ((i,j) {\text が空きマス}, S_{i,j} \neq \emptyset) \end{cases}$

が成り立つ. この更新式に従って, 適切な順番で更新することによって, 計算量 $O(HW)$ で, ${\rm DP}[1,1]$ によって解答を導くことができる.