개구리의 여행 (학습중)

어떤 호수에 개구리 한마리가 살고 있습니다. 이 개구리는 여행을 무척 좋아합니다.

호수에는 N×N 크기의 정사각형 형태로 돌이 있으며, 개구리는 돌 위에서 돌아다닐 수 있습니다. 각 돌의 위치는 좌표로 표현할 수 있는데, 위에서부터 i번째, 왼쪽부터 j번째 위치를 (i, j)로 표현합니다. 따라서 가장 왼쪽 위에 있는 돌의 좌표는 (1, 1)이며 가장 오른쪽 아래에 있는 돌의 좌표는 (N, N)입니다.

개구리가 모든 위치를 자유롭게 돌아다닐 수 있다면 좋겠지만, 안타깝게도 이 호수에는 개구리가 갈 수 없는 위험한 돌도 있습니다. 구체적으로 보면 호수에는 세 종류의 돌, 안전한 돌, 미끄러운 돌, 천적이 사는 돌이 있습니다. (i, j) 위치의 돌의 종류는 Ai,j​로 표현되며, 만약 Ai,j​가 .이라면 (i, j) 위치에는 안전한 돌이, S라면 미끄러운 돌이, #이라면 천적이 사는 돌이 있다는 뜻입니다.

개구리의 여행은 시작 위치 (r1​, c1​)과 도착 위치 (r2​, c2​)를 정한 뒤, 시작 위치에서 도착 위치까지 가는 것이 목표입니다. 개구리의 초기 점프력은 1이며, 개구리는 여행 과정에서 다음과 같은 행동을 할 수 있습니다.

1. 점프
   • 현재 위치에서 상하좌우 방향 중 하나를 골라 현재 점프력만큼의 칸을 이동합니다. 엄밀하게는, 현재 위치가 (x, y)이고 점프력이 k라면 (x−k, y), (x+k, y), (x, y−k), (x, y+k) 중 하나의 위치로 이동 가능합니다.
   • 단, 이동하려는 위치에 돌이 없다면 그 위치로는 이동이 불가능하며, 만약 도착한 위치에 미끄러운 돌이 있다면 위험하기 때문에 그 위치로 이동할 수 없습니다. 또한, 점프해서 도착하는 위치나 점프하면서 지나치는 경로에 천적이 사는 돌이 있는 경우에도 매우 위험하기 때문에 점프할 수 없습니다.
   • 점프에는 1만큼의 시간이 소요됩니다.
2. 점프력 증가
   • 점프력을 1만큼 증가시킵니다.
   • 기존 점프력이 1, 2, 3, 4 중 하나인 경우에만 가능합니다. 즉, 증가한 뒤 개구리의 최대 점프력은 5입니다.
   • 점프력 증가 후 점프력을 k라고 할 때, k2만큼의 시간이 소요됩니다.
3. 점프력 감소
   • 점프력을 감소시킵니다.
   • 기존 점프력이 k인 경우 1, 2, ⋯, k−1중 하나의 점프력을 갖도록 만들 수 있습니다.
   • 점프력 감소에는 1만큼의 시간이 소요됩니다.

개구리는 이 호수에서 총 Q번의 여행 계획을 세웠습니다. 개구리는 각 계획마다 최대한 짧은 시간에 여행을 마치고자 합니다. 호수에 있는 돌의 정보와 개구리의 여행 계획들이 주어질 때, 각 여행에 걸리는 최소 시간을 출력하는 프로그램을 작성하세요. 만약 도착이 불가능한 계획이 있다면 그 계획에 대한 답으로는 -1을 출력합니다.

 

입력 예제

예제 1

입력

8
.S..#.##
##.S.##.
##S#S##S
..SS.S##
.S#S.#S#
..#S...#
###....S
#.S.SS#.
5
1 1 1 3
4 1 4 5
6 2 1 1
7 4 8 8
8 2 6 1

출력

5
15
25
-1
27

https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/frog-journey/description

 

추천인 : lipbutter94