matthew as a q.

目標10記事quant

計算量削減メモ

# 事前処理で定数時間化

 

## 題材

https://atcoder.jp/contests/abc129/tasks/abc129_d

 

## 具体的には

なりでは、各地点に対して上下左右の探索が必要で、O(HW(H+W))となり、H、Wが2000以下の正の整数のため、時間内に計算間に合わず。

 

各地点での上下左右の探索を予め実施して記録しておくことで、O(HW)に落とせる。