AtCoder-ABC210 D - National Railway【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210720213139p:plain

AtCoder Beginner Contest210のD問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 210 - AtCoder

AtCoder Beginner Contest210 D - National Railway

問題文

高橋王国は H 行 W 列のグリッドで表されます。北から i 行目、西から j 列目のマスを (i,j) で表します。

このたび、高橋王国の国民から交通の利便性のために鉄道の建設を求める声が多数寄せられ、国王の高橋君は鉄道を建設しなければならなくなりました。
鉄道建設は以下の 2 つのステップからなります。

・まず、2 つの異なるマスを選び、それぞれに駅を建設する。マス (i,j) に駅を建設すると Ai,j 円の費用がかかる。
・その後、建設した 2 つの駅を結ぶ線路を建設する。2 つの駅がマス (i,j) とマス (i′,j′) にあるとき、これらを結ぶ線路の建設をすると C×(|i−i′|+|j−j′|) 円の費用がかかる。（ここで、|x| は x の絶対値を表す。）
高橋君は国民の利便性を上げることよりも、鉄道建設にかかる費用を少なく抑えることを優先したいと考えています。
鉄道建設にかかる費用として考えられる最小値を出力してください。

制約

・2≤H,W≤1000
・1≤C≤10^9
・1≤Aij≤10^9
・入力はすべて整数

解答例

h, w, c = map(int,input().split())

A = []
for i in range(h):
    array = list(map(int, input().split()))
    A.append(array)

INF = int(1e18)

ans = INF

for _ in range(2):
    # dp[i][j]はi,jのときのAij - c*(i+j)の最小値
    dp = [[INF for _ in range(w)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if i > 0:
                dp[i][j] = min(dp[i][j], dp[i-1][j])
            if j > 0:
                dp[i][j] = min(dp[i][j], dp[i][j-1])
            ans = min(ans, A[i][j] + c*(i+j) + dp[i][j])

            dp[i][j] = min(dp[i][j], A[i][j] - c*(i+j))

    A.reverse()        

print(ans)