AtCoder Beginner Contest 129 D - Lamp
問題概要
障害物と何も無いマスで構成されたグリッドが与えられる。障害物の無いマス1つにランプを置く。ランプの光線は上下左右方向で障害物に衝突するまで1直線に進む。
ランプを置くマスを上手く調整した時、考え得る照らされるマス目の最大値は幾らか。
解法
愚直に実装するととなり、TLEとなってしまう。そのため、各マス目に対し、上下左右方向それぞれからどれだけ照らされるかを考えることにより計算量を減らす。
具体的には、上下左右方向用の4つの配列を用意し、それぞれの方向に累積させていく。各方向に対し、グリッドの淵の部分は例外処理を行うことに注意。これを実装して、AC。。
