AtCoder Beginner Contest 129 lamp
D問題のlampを解いてみた。
- 上下左右でそれぞれの地点から障害物もしくは端にぶつかるまでの距離を算出し、行列化する。
- 距離の計算は、行または列の番号を+1するとともに距離の数値を+1、障害物にぶつかった場合値を-1にする処理で求まる。障害物があるグリッドの値を便宜的に-1にしておくと、その次のインクリメントで隣のグリッドの距離の値が0になり、いい感じに。
- 上下左右に1列最初に追加しておき、追加した分のグリッドを-1としておく。
- 二次元配列ははnumpyでやった方がやりやすい。行列どうしを足したり引いたりもnumpyなら簡単。
- 最後に光源を置いているグリッドの分+1する。
# 上下左右の壁までの距離の行列
def max_grid_num():
raw_input = input().split()
H = int(raw_input[0])
W = int(raw_input[1])
grid_matrix = raw_input[2:]
from_up_range = (range(1, H+1), range(1, W+1))
from_low_range = (range(H, 0, -1), range(1, W+1))
from_left_range = (range(1, H+1), range(1, W+1))
from_right_range = (range(1, H+1), range(W, 0, -1))
cumsum_matrix = np.zeros((H+2, W+2))
for (y_range, x_range), (before_y, before_x) in ((from_up_range, (-1, 0)), (from_low_range, (1, 0)),
((from_left_range), (0, -1)), (from_right_range, (0, 1))):
each_num_matrix = np.full((H+2, W+2), -1)
for y in y_range:
for x in x_range:
if grid_matrix[y-1][x-1] == '#':
each_num_matrix[y][x] = -1
else:
each_num_matrix[y][x] = each_num_matrix[y+before_y][x+before_x] +1
cumsum_matrix += each_num_matrix
return int(cumsum_matrix.max()+1)
こうした方がいい、というのあったらアドバイスお願いします！