시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB146717814320.576%

문제

시루는 부모님과 함께 백화점에 갔다. 부모님은 쇼핑할 것이 많기 때문에 여러 곳을 돌아다녀야 하고, 시루는 부모님과 함께 걸어다니는 것이 너무 힘들어서 의자에 앉아서 쉬려고 한다.

백화점은 세로 길이가 $N$, 가로 길이가 $M$인 격자 형태이고, 상하좌우로 인접한 칸으로 이동할 때마다 1 만큼의 체력을 소모한다. 시루는 현재 위치에서 출발해 백화점 곳곳에 있는 의자 중 하나를 찾아가서 앉으려고 한다. 시루는 백화점 밖으로 나가면 부모님께 혼나기 때문에 백화점 밖으로 나갈 수 없다.

백화점에는 건물을 지탱하기 위한 기둥과 옷을 전시하기 위한 마네킹이 있다. 시루는 기둥이 있는 칸으로 이동하지 못하고, 마네킹을 무서워하기 때문에 마네킹과 거리가 $K$ 이하인 칸은 사용하지 않으려고 한다. 이때 두 칸 $(r_x, c_x), (r_y, c_y)$의 거리는 $\vert r_x-r_y \vert + \vert c_x-c_y \vert$이다. 단, 시루가 출발할 때는 부모님과 함께 있기 때문에, 출발 지점과 마네킹과의 거리가 $K$ 이하가 되어도 출발할 수 있다.

시루는 다리가 너무 아프기 때문에 체력 소모를 최소화하면서 의자까지 찾아가려고 한다. 시루가 소모하는 체력의 최솟값을 구해보자.

입력

첫째 줄에 백화점의 세로 길이, 가로 길이, 마네킹과 떨어져야 하는 거리를 의미하는 정수 $N, M, K$가 공백으로 구분되어 주어진다. ($1 \leq N,M \leq 2\,000$, $0 \leq K \leq 4\,000$)

둘째 줄부터 $N$개의 줄에 각각 $M$개씩 위에서부터 차례로 백화점의 상태가 주어진다. 아무것도 없는 칸은 0, 기둥이 있는 칸은 1, 의자가 있는 칸은 2, 마네킹이 있는 칸은 3, 시루의 시작 위치는 4로 주어진다. 시루의 시작 위치는 정확히 한 번 주어지고, 해당 위치에 기둥, 의자, 마네킹이 존재하지 않는다.

출력

시루가 의자를 찾아갈 수 있다면 시루가 소모하는 체력의 최솟값을 출력한다.

만약 의자를 찾아갈 수 없다면 -1을 출력한다.

예제 입력 1

5 5 1
0 0 0 0 4
0 0 0 1 0
0 0 0 0 3
0 0 0 1 0
0 0 0 0 2

예제 출력 1

8

예제 입력 2

5 5 2
0 0 0 0 4
0 0 0 1 0
0 0 0 0 3
0 0 0 1 0
0 0 0 0 2

예제 출력 2

-1

예제 입력 3

5 5 2
2 0 0 0 4
0 0 0 1 0
0 0 0 0 3
0 0 0 1 0
0 0 0 0 0

예제 출력 3

4

예제 입력 4

5 5 0
0 0 0 0 4
0 0 0 1 0
0 0 0 0 3
0 0 0 1 0
0 0 0 0 0

예제 출력 4

-1

힌트

Python 사용자는 PyPy로 제출하는 것을 권장합니다.

출처

University > 연세대학교 미래캠퍼스 > 2022 연세대학교 미래캠퍼스 슬기로운 코딩생활 D번