초강력 드릴 (Powerful Drill)

문제

인덱스국 문화사 : Day 3

당신은 인덱스국 광산에서 금을 찾기 위에 몰려든 10100명가량의 모험가들 중 한 명입니다.

당신은 금을 찾기 위해서 만반의 준비를 한 상태입니다.

당신의 조사 결과, 인덱스국의 광산은 지하 3층으로 이루어져 있고, 크기는 세로 R미터, 가로 C미터로 이루어져 있다고 합니다. 지하 1층은 일반인에게 개방되어 있고, 지하 3층에는 금이 묻혀 있다고 알려져 있습니다. 문제의 지하 2층은 단단한 돌로 막혀 있어서 들어갈 수 없는 상태 입니다. 그러나 당신은 초강력 드릴을 2(R + C)개 들고 왔기 때문에, 돌 같은 건 쉽게 부숴버릴 수 있습니다. 이 드릴들은 매우 강력해서 지나가는 길에 있는 1m × 1m 돌들을 전부 부숴 길로 만들어버릴 수 있지만, 이동 방향은 고정되어 바꿀 수 없습니다. 드릴들은 북쪽과 남쪽에 각각 C개, 서쪽과 동쪽에 각각 R개 설치되어 있고, 각각의 드릴은 이동하는 데 드는 비용이 정해져 있습니다. 놀랍게도 다 쓴 드릴을 치우는 데는 비용이 들지 않는다고 합니다.

설치된 드릴들의 모습 당신은 가장 북서쪽 격자 위에 떨어지려고 합니다. 금의 위치는 가장 남동쪽 격자로 추측하 고 있습니다. 당신은 떨어지기 전에 미리 드릴들을 이용해서 가장 북서쪽 격자와 가장 남동쪽 격자 사이를 이동할 수 있도록 만드려고 합니다. 당신은 금을 얻기 위해 드는 비용을 최소화하는 프로그램을 작성하려고 합니다.

구현 세부 사항

다음 함수를 구현하세요.

int64 getDrillMovingCost(int N[][], int S[][], int W[][], int E[][])

• 이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.
• N, S는 각 원소가 크기 R의 배열이 되는 크기 C의 배열입니다. 모든 0 ≤ i ≤ C − 1, 0 ≤ j ≤ R − 1에 대해 N[i][j]는 광산 북쪽에 있고 광산 서쪽에서 i + 0.5미터 떨어져있는 드릴이 j미터 이동한 상태에서 1미터 더 이동하기 위한 비용이고, S[i][j]는 광산 남쪽에 있고 광산 서쪽에서 i + 0.5미터 떨어져있는 드릴이 j미터 이동한 상태에서 1미터 더 이동하기 위한 비용입니다.
• W, E는 각 원소가 크기 C의 배열이 되는 크기 R의 배열입니다. 모든 0 ≤ i ≤ R − 1, 0 ≤ j ≤ C − 1에 대해 W[i][j]는 광산 서쪽에 있고 광산 북쪽에서 i + 0.5미터 떨어져있는 드릴이 j미터 이동한 상태에서 1미터 더 이동하기 위한 비용이고, E[i][j]는 광산 동쪽에 있 고 광산 북쪽에서 i + 0.5미터 떨어져있는 드릴이 j미터 이동한 상태에서 1미터 더 이동하기 위한 비용입니다.
• 이 함수는 가장 북서쪽 격자와 가장 남동쪽 격자 사이를 이동하기 위한 최소 비용을 반환 해야 합니다.

제한 조건

• 1 ≤ R, C ≤ 500
• 1 ≤ N[i][j], S[i][j], W[j][i], E[j][i] ≤ $10^9$ (0 ≤ i ≤ C − 1, 0 ≤ j ≤ R − 1)

서브태스크

서브태스크	점수	R, C
1	2	R, C ≤ 3
2	8	R ≤ 7,
3	4	R, C ≤ 50
4	6	R, C ≤ 500

예제 입출력

그레이더는 다음 함수를 호출합니다.

getDrillMovingCost([[2, 2, 2], [2, 2, 2], [1, 1, 1]], [[5, 9, 1], [3, 3, 3], [6, 9, 7]] ,[[2, 2, 2], [3, 3, 3], [8, 7, 9]],[[7, 9, 8], [2, 2, 2], [1, 1, 1]]) = 7

샘플 그레이더

Sample Grader는 다음과 같은 형식으로 입력을 받습니다.

• line 1 : R C
• line 2 + i (0 ≤ i ≤ C − 1) : N[i][0] N[i][1] ··· N[i][R − 1]
• line 2 + C + i (0 ≤ i ≤ C − 1) : S[i][0] S[i][1] ··· S[i][R − 1]
• line 2 + 2C + i (0 ≤ i ≤ R − 1) : W[i][0] W[i][1] ··· W[i][C − 1]
• line 2 + R + 2C + i (0 ≤ i ≤ R − 1) : E[i][0] E[i][1] ··· E[i][C − 1]