실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
도시는 N×N 정사각형의 필드(3 ≤ N ≤ 100)로 구성되어 있고, 각 블록은 N−1 개의 북쪽-남쪽 도로와 N−1 개의 동쪽-서쪽 도로로 구분됩니다. 큰 담이 도시의 외곽을 둘러싸고 있어 아이가 도시를 떠나는 것을 방지합니다. 아이는 블록 사이의 도로를 건너기 전 양쪽을 신중히 살피면서 어떤 블록에서든 인접한 다른 블록으로 자유롭게 이동할 수 있습니다. 도로를 건너는데 필요한 시간은 T 단위입니다 (0 ≤ T ≤ 1,000,000).
어느 날, 아이는 친구의 집에서 체스를 하기 위해 북서쪽 구석 블록에서 시작하여 친구의 집이 있는 남동쪽 구석 블록에 가기로 결정했습니다. 도중에 아이는 배가 고플때마다, 아이는 방문하는 모든 세 번째 블록마다 정지하여 간식을 먹습니다 (시작 블록은 포함하지 않고,친구의 집이 위치한 마지막 블록은 포함할 가능성이 있음). 몇몇 블록은 다른 블록보다 더 많은 간식이 있으므로, 간식을 먹기위해 멈추는 시간은 멈춘 블록에 따라 달라집니다.
아이가 친구의 집에 도달하는데 걸리는 최소 시간을 구하는 것을 도와주세요.
입력의 첫 번째 줄에는 N과 T가 들어있습니다. 다음 N 줄에는 각각 N개의 양의 정수가 포함되어 있습니다 (각각 100,000 이하). 이들은 각 블록드에서 간식을 먹는 데 필요한 시간을 설명합니다. 첫 번째 줄의 첫 번째 숫자는 북서쪽 구석입니다.
아이가 친구의 집으로 이동하는데 필요한 최소 시간을 출력하세요.
4 2 30 92 36 10 38 85 60 16 41 13 5 68 20 97 13 80
31
이 예시에 대한 최적의 해결책은 3개의 정사각형 이동("10"을 먹는다). 그 다음 남쪽으로 두 번, 서쪽으로 한 번 이동("5"를 먹는다). 그리고 마지막으로 남쪽과 동쪽으로 목표지점으로 이동한다.
출처: USACO 2017 February Contest, Gold Problem 1. Why Did the Cow Cross the Road