ABC037 D 経路
問題概要
縦 横 のマス目があり、それぞれのマスには整数 が書かれている。
このグリッドの中の好きなマスから開始し、今いるマスの上下左右に隣接しているマスのうち、今いるマスより大きな整数が書かれたマスに移動することができる(移動しなくてもよい)。
ありうる移動経路の個数を で割った余りを求めよ。
制約
解法
dp[ ][ ] := マス で動くのを終了する場合の移動経路の個数
として、 が大きい順に dp[ ][ ] を計算していく。
dpテーブルは全て1で初期化しておき、dpテーブルの更新は、マス の4近傍のマス に対して、
dp[ ][ ] dp[ ][ ];
をする。
すべてのマス に対してdp[ ][ ] の総和が答えとなる。