ABC129-D_Lampをpythonで解いた（動的計画法）

問題

• ABC129-D_Lamp

問題概要

任意のマスから光線が上下左右に伸びる（ただし、障害物は透過しない）。 明かりによって照らされるマスの個数を最大値を計算する。

解法

• 障害物のあるグリッドなので、幅優先探索などの方法が考えられるが、上下左右にしか光線は伸びないので、ここはDPで解いていくのが良いと思われる。

方針

• 今回の場合漸化式を解く際に一度にマスの計算をすることは難しい（理由は口頭で）。
  なので今回は以下のテーブルを準備する。 $$$ U[i][j] : \quad 上に何マス照らせるマスがあるか？\ D[i][j] : \quad 下に何マス照らせるマスがあるか？\ R[i][j] : \quad 右に何マス照らせるマスがあるか？\ L[i][j] : \quad 左に何マス照らせるマスがあるか？ $$$ （ただし、$$D[i][j]、R[i][j]$$に関してはループの回す方向に注意する。）

更新式

$$$ U[i][j] = U[i-1][j] + 1\ D[i][j] = D[i+1][j] + 1\ R[i][j] = R[i][j+1] + 1\ L[i][j] = L[i][j-1] + 1 $$$ もし障害物のマスの場合は $$$ U[i][j] = 0\ ... $$$

最後合計のマスを計算する際、重複しているマス数3を引いておく。

コード

H,W = map(int,input().split())
S = [input() for i in range(H)]

U = [[0]*W for i in range(H)]
D = [[0]*W for i in range(H)]
R = [[0]*W for i in range(H)]
L = [[0]*W for i in range(H)]

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            U[i][j] = 0
        elif i == 0 and S[i][j] == '.':
            U[i][j] = 1
        else:
            U[i][j] = U[i-1][j] + 1
            
    for j in range(W):
        if S[i][j] == '#':
            L[i][j] = 0
        elif j == 0 and S[i][j] == '.':
            L[i][j] = 1
        else:
            L[i][j] = L[i][j-1] + 1
            
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if S[i][j] == '#':
            D[i][j] = 0
        elif i == H-1 and S[i][j] == '.':
            D[i][j] = 1
        else:
            D[i][j] = D[i+1][j] + 1
            
    for j in range(W-1,-1,-1):
        if S[i][j] == '#':
            R[i][j] = 0
        elif j == W-1 and S[i][j] == '.':
            R[i][j] = 1
        else:
            R[i][j] = R[i][j+1] + 1
            
ans = 0 

for i in range(H):
    for j in range(W):
        ans = max(ans,U[i][j]+R[i][j]+D[i][j]+L[i][j]-3)        
print(ans)    

written by 友達のtaniponyo