https://atcoder.jp/contests/abc210/tasks/abc210_d
시간 2초, 메모리 1024MB

input :

• H W C (2 ≤ H, W ≤ 1000, 1 ≤ C ≤ 109)
• 각 배열의 원소 (1 ≤ Aij ≤ 109

output :

• Print the minimum possible total cost of the construction of the railway.
  철로를 설치하는데에 가능한 최솟값을 출력하시오.

조건 :

• First, choose two different squares and build a station on each of them. It costs Aijyen to build a station on the square (i, j).
  첫째로, 역을 세울 두 위치를 선택합니다. 각 역을 설치하는 데에는 Aij엔만큼 소요됩니다.

• Then, build a railway track connecting these two stations. This costs C (|i - i'| + |j - j'|) yen when the two stations are on the squares (i, j) and (i', j').
  그리고 두 역을 연결하는 철로를 건설합니다. 이 비용은 C (위치의 절댓값)만큼 소요됩니다.

---

각 모든 위치를 찾아내는 것은 시간이 매우 오래 걸린다.
다른 방법이 필요하다.

기록

모든 지점을 확인은 해야 한다. 이를 특정한 방향으로 만들 수는 없을까?
특정 지점에서 아래, 오른쪽으로 이동해가면서 최솟값을 기록하게 하고.
위의 방법과 방향을 반대로 아래, 왼쪽으로 이동해 가면서 최솟값을 기록하게 해서 정답을 구해보자.

각 지점을 지나갈 때 마다 현재의 지점을 역으로 세울지, 이전의 최소값에 철로를 건설하는 방안을 사용할 지 결정짓자.

dp[x + 1][y + 1] = min(a[x][y], dp[x][y + 1] + c, dp[x + 1][y] + c)
를 점화식으로 사용하자.
어차피 각 지점의 절대값 차이가 1밖에 안되서 c만 더해주면 된다.

그리고 철로를 깔았다면 여기에 역을 세워서 철로를 마무리 할 수 있다.
이를 정답으로 계속 업데이트 ㅎ자ㅏ.

import sys


def check(input):
    global ans

    dp = [[float('inf')] * (w + 1) for _ in range(h + 1)]
    for x in range(h):
        for y in range(w):
            a, from_left, from_up = input[x][y], dp[x][y + 1] + c, dp[x + 1][y] + c
            dp[x + 1][y + 1] = min(a, from_left, from_up)

            ans = min(ans, from_left + a, from_up + a)


h, w, c = map(int, sys.stdin.readline().split())
data = []
for _ in range(h):
    temp = list(map(int, sys.stdin.readline().split()))
    data.append(temp)
ans = float('inf')

check(data)
check(data[::-1])
print(ans)

2차원 배열도 1차원 배열이 여러개 쌓여있는 것이기에 data[::-1]을 이용해서 뒤집어 줄 수 있다.