AtCoder Beginner Contest 232 D 問題 Weak Takahashi
問題
提出解答
問題の概要
縦 行, 横
列の
マスからなるグリッドがある. 各マスは空きマスか, 壁である. 空きマス
にいるとき,
のうち, 空きマスが存在するならば, その空きマスから1つ選んで移動できる (場外禁止).
空きマス から移動するとき, 最大何マス通るか?
制約
は空きマス
解法
動的計画法で解く. でマス
から始めたときに通る最大のマスの数とする. そして,
で, マス
から移動できるマスの集合とする. このとき,
が成り立つ. この更新式に従って, 適切な順番で更新することによって, 計算量 で,
によって解答を導くことができる.