README.md

[Gold II] 호석사우루스 - 22255

문제 링크

성능 요약

메모리: 17728 KB, 시간: 228 ms

분류

데이크스트라, 그래프 이론, 최단 경로

제출 일자

2023년 11월 16일 09:24:30

문제 설명

음머... 미련한 소인 호석사우루스는 융통성 따위 일절 가지지 않는다. 자신의 철칙에 맞게 우직하게 미궁을 탈출하려고 한다. 미궁은 N$N$행 M$M$열의 격자로 이루어져 있고 각 칸마다 입장하는 순간 받는 충격량이 있다. 같은 방을 여러 번 들어가면, 들어갈 때마다 같은 충격량을 받게 된다. 당연히 똑똑한 소라면 최소의 충격을 받으면서 미궁을 탈출하던가, 애초에 미궁에 안 빠지도록 머리를 썼겠지만, 호석사우루스는 그런 거 없다!

그의 철칙은, 이동 방식에 있다. 매 이동 시 마다 움직일 수 있는 방향이 다르다.

•  3K$3K$ 번째 이동 시에는 상, 하, 좌, 우로 인접한 곳 중 한 칸으로 이동할 수 있다.
•  3K+1$3K+1$ 번째 이동 시에는 상, 하로 인접한 곳 중 한 칸으로 이동할 수 있다.
•  3K+2$3K+2$ 번째 이동 시에는 좌, 우로 인접한 곳 중 한 칸으로 이동할 수 있다.
• 만약 이동하려는 곳에 벽이 있으면 이동할 수 없다.
• 최초의 이동은 1번째 이동이고, 이후에 2번째, 3번째 이동이다.

자신의 철칙을 지키되, 아픈 건 싫어하는 호석사우루스를 도와서 탈출구까지의 최소 충격량을 구해주자!

입력

첫 번째 줄에 격자의 크기 N$N$, M$M$이 주어진다.

두 번째 줄에 시작 지점과 도착 지점의 정보인 Sx$S_x$, Sy$S_y$, Ex$E_x$, Ey$E_y$ 가 공백으로 구분되어 주어진다. 시작 지점이 Sx$S_x$행 Sy$S_y$열이며 도착 지점이 Ex$E_x$행 Ey$E_y$열임을 의미한다. 시작 지점과 도착 지점은 항상 다르다.

세 번째 줄부터 N$N$ 개 줄에 걸쳐서 지도의 정보가 주어진다. 각 줄마다 M$M$ 개의 정수가 주어진다. i+2$i+2$번 줄의 j$j$번째 숫자는 i$i$행 j$j$열에 위치한 격자의 충격량을 의미한다. 만약 충격량 정보가 −1$-1$이라면 해당 격자는 벽임을 의미한다.

시작점과 도착점의 충격량은 0 임이 보장된다.

출력

첫 번째 줄에 호석사우루스가 탈출하는 과정에서 받는 최소 충격량을 출력한다. 만약 탈출하지 못한다면 −1$-1$ 을 출력한다.