연습문제

산타의 텔레포트

난이도
Lv. 4
제출
147 명
참가자
20 명
정답률
18.18 %
지원 언어
C
C++
Java
Python
JavaScript
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
JavaScript 1초 1024MB
C++ 1초 1024MB
C 1초 1024MB
Java 2초 1024MB
Python 1초 1024MB

n * m 크기의 격자 모양으로 이루어진 마을이 있습니다. 산타는 현재 (1, 1) 위치에 있고, 선물 배달을 위해 (n, m) 위치로 이동하려고 합니다.



마을의 각 칸은 -2, -1, 0, 그리고 10 이상의 수들로만 이루어져 있습니다. -2는 선물을, -1은 벽을, 0은 빈 칸을, 그리고 10 이상의 수들은 텔레포트가 가능한 공간임을 뜻합니다. 산타는 상하좌우 인접한 칸 중 벽이 아닌 칸으로 이동하는 것이 가능하며 이러한 이동에는 에너지가 전혀 소모되지 않습니다. 하지만 10 이상의 수로 이루어진 텔레포트 공간에서는 같은 수가 적혀있는 칸으로 텔레포트를 하는 것이 가능하며, 이때는 에너지가 1만큼 소모됩니다.



성공적인 선물 배달을 위해 산타는 꼭 이동 도중 선물을 챙겨야 한다 했을 때, 도착지에 도달하기 위해 소모해야만 하는 최소 에너지를 구하는 프로그램을 작성해보세요.




단, 텔레포트가 가능한 칸에서도 상하좌우 인접한 칸으로 이동해도 됨에 유의합니다.



본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.

제약조건

  • 2 ≤ n, m ≤ 500
  • 10 ≤ 텔레포트로 가능한 수 ≤ 100,000

입력형식

첫 번째 줄에는 격자의 크기를 나타내는 n, m 값이 공백을 사이에 두고 주어집니다.

두 번째 줄 부터는 n개의 줄에 걸쳐 각 행에 해당하는 정보가 주어집니다. 각 행은 m개의 수로 이루어져 있으며, 공백을 사이에 두고 주어집니다. 각 칸은 -2, -1, 0, 그리고 10 이상의 수로만 이루어져 있으며, -2는 선물을, -1은 벽을, 0은 빈 칸을, 그리고 10 이상의 수들은 텔레포트가 가능한 공간임을 뜻합니다.

선물은 정확히 하나만 주어지며, (1,1)칸과 (n, m)칸은 항상 빈 칸으로 주어짐을 가정해도 좋습니다.

출력형식

첫 번째 줄에 도착지에 도달하기 위해 소모해야 하는 최소 에너지를 출력합니다. 만약 선물을 챙겨 도착지에 도달하는 것이 불가능하다면 -1을 출력합니다.

입력예제1

8 8
00 22 -1 00 00 -1 33 00
00 11 -1 00 11 -1 00 11
-1 -1 -1 -1 -1 -1 -1 -1
00 22 -1 33 44 -1 00 00
00 00 -1 00 -2 -1 00 00
-1 -1 -1 -1 -1 -1 -1 -1
00 22 -1 22 00 -1 22 44
00 00 -1 00 33 -1 00 00
출력예제1

3

첫 번째 예제에서는 처음 (2, 2)로 이동하여 텔레포트를 타고 (2, 8)로 이동합니다. 다시 (1, 7)로 이동하여 텔레포트를 타고 (4, 4)로 이동합니다. (5, 5)에 놓여 있는 선물을 찾아 (4, 5)로 이동하여 텔레포트를 타고 (7, 8)로 이동합니다. 이제 텔레포트 없이 (8, 8)에 도달이 가능하므로 에너지를 3만큼 소모하여 선물 배달이 가능합니다.

입력예제2

5 5
00 11 11 11 11
11 11 11 11 11
11 11 -2 11 11
11 11 11 11 11
11 11 11 11 00
출력예제2

0

두 번째 예제에서는 텔레포트를 이용하지 않고 선물을 챙겨 도착지에 도달하는 것이 가능하므로 답은 0이 됩니다.

목록