jtw7913   1년 전


설명

검의 해안(Sea of Sword Coast) 지역은
$n \times n$ 크기의 구역으로 나눌 수 있다.
($1 \leq n \leq 50$)

각 구역은 서로 다른 해양 특성을 가진다.
한 구역에서 배는 북, 남, 동, 서 인접한 구역으로만 이동할 수 있다(존재한다면).

한 구역에서 인접한 구역으로 이동하는 데 걸리는 시간은 도착지 구역에만 의존한다.
이 시간은 양의 정수이며, 최대 1000이다.

예를 들어,
$t[4,4] = 10$ 이라면, 구역
$(3,4), (5,4), (4,5), (4,3)$
에서 $(4,4)$로 이동하는 데 10시간이 걸린다.

그러나 항해 중 방향 전환은 쉽지 않다.
선원들은 바람 방향의 변화를 다루어야 하고,
배도 속도를 줄였다가 다시 가속해야 한다.

이상하게도, 배가 이미 어떤 방향으로 이동 중이라면
진로를 바꾸는 데는 항상 정확히 3시간이 추가로 든다.

예를 들어,

  • $t[4,4] = 10$, $t[4,5] = 20$ 이라면,
    구역 $(4,3) \to (4,4) \to (4,5)$ 를 항해하는 데는
    $10 + 20 = 30$ 시간이 걸린다.

  • 하지만 $(3,4) \to (4,4) \to (4,5)$ 의 경우,
    방향을 바꾸어야 하므로
    $10 + 20 + 3 = 33$ 시간이 걸린다. 

지금 마법사 엘민스터는 구역 $(1,1)$에 있고,
가능한 한 짧은 시간 안에 발더스 게이트 $(n,n)$ 에 도착하고자 한다.

최단 시간을 구하라. (모든 방향 전환 시간도 포함해야 한다.)

입력

  • 첫 줄: 정수 $n$

  • 다음 $n$개의 줄: 각 구역의 이동 시간 배열 $t$ 가 주어진다.

    • 두 번째 줄: $t[1,1], t[1,2], \dots, t[1,n]$

    • 세 번째 줄: $t[2,1], t[2,2], \dots, t[2,n]$

    • …

    • $(n+1)$번째 줄: $t[n,1], t[n,2], \dots, t[n,n]$

항상 $t[1,1] = 0$ 이다.

출력

  • 엘민스터가 $(1,1)$에서 $(n,n)$까지 도달하는 데 필요한 최소 시간을 출력한다.


댓글을 작성하려면 로그인해야 합니다.