만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

외계인의 여정

면접 대비

시간 제한5초메모리 제한2048 MB

요약
높이 격자에서 한 변의 길이가 l인 정사각형 우주선이 왼쪽 위에서 오른쪽 아래까지 이동하는 데 필요한 최소 연료를 구합니다.
난이도

보통10점 중 6점

유형
최단 경로, 슬라이딩 윈도우, 행렬
정답자
아직 제출이 없습니다

문제

작은 외계인이 정사각형 우주선을 타고 도시 건너편에 있는 차원 간 게이트까지 가야 합니다. 연료가 거의 남지 않아서, 도시를 가로지르는 데 필요한 최소 동력을 구해 달라고 부탁합니다. 연료 1단위로 우주선을 높이 1단위 들어 올릴 수 있습니다.

우주선은 이동하는 동안 아래에 있는 모든 칸 위를 지나야 합니다. 우주선은 연료 없이 북, 남, 동, 서 방향으로 움직일 수 있으며, 우주선 전체는 항상 지도 안에 있어야 합니다.

우주선은 처음에 지면 위에 놓여 있고, 그 영역의 높이는 0입니다. 우주선의 왼쪽 위 모서리 칸은 지도의 왼쪽 위 모서리 칸과 겹쳐 있으며, 우주선의 네 변은 격자에 맞춰져 있습니다. 지면 위에 떠 있으려면 우주선의 바닥이 아래에 있는 모든 지면 칸보다 엄격하게 높아야 합니다. 우주선은 정수 단위로만 들어 올릴 수 있습니다.

우주선의 오른쪽 아래 모서리 칸이 지도의 오른쪽 아래 모서리 칸 위에 떠 있으면 목적지에 도착한 것입니다.

지도는 hh행 ww열의 격자이며, 각 칸에는 해수면 기준 높이가 있습니다. 우주선은 한 변의 길이가 ll인 정사각형이고, 1≤l<min⁡(h,w)1 \leq l < \min(h, w)입니다.

외계인에게 필요한 연료의 최솟값을 구하세요.

입력

첫 줄에 세 정수 hh, ww, ll이 주어집니다. 범위는 1≤h≤5001 \leq h \leq 500, 1≤w≤5001 \leq w \leq 500, 1≤l<min⁡(h,w)1 \leq l < \min(h, w)입니다.

이어서 hh줄에 걸쳐 각 줄마다 ww개의 정수가 주어집니다. 각 정수는 [0,109][0, 10^9] 범위의 양의 정수입니다. i번째 줄의 j번째 정수는 i행 j열 칸의 높이입니다.

출력

우주선으로 도시를 가로지르는 데 외계인이 필요한 동력의 최솟값을 출력합니다.

예제3

  1. 예제 1

    입력
    5 5 2
0 0 1 1 3
0 0 1 1 3
3 3 1 1 3
3 3 1 1 1
3 3 1 1 1
    예상 출력
    2

  2. 예제 2

    입력
    6 6 1
0 1 2 3 4 5
0 1 2 3 4 5
0 1 1 1 1 5
0 3 4 5 6 7
0 3 0 0 0 7
0 0 0 1 0 0
    예상 출력
    1

  3. 예제 3

    입력
    3 3 2
0 0 7
0 0 7
9 7 9
    예상 출력
    10