문제
N × N 의 행렬로 지형도가 표시된 산이 있다.
행렬의 원소의 값은 양의 정수값으로 그 위치에서의 높이를 말해준다.
등산가들은 산의 바깥 지역(높이 0)으로부터 정상에 도달하기 위하여 가장 경제적인 루트를 탐색하려고 한다.
경제적인 경로란 힘을 가장 적게 들이고 정상까지 올라갈 수 있는 길을 말한다.
예를 보면서 설명해보자. 다음은 행렬 Mount[5,5]로 표시된 산악 지형이다.
산의 정상은 Mount[3,3]의 위치에 있으며, 그 높이는 6이다.
그리고 이 산의 바깥지 역은 모두 해발이 0이다.
등산가가 산에 오르는 시작점의 위치는 산의 바깥 지역의 어디에서 시작해도 좋다.
등산가는 어떤 한 지역에서 그 위치에 인접한 네 방향(위, 아래, 왼쪽, 오른쪽)으로만 움직일 수 있다.
인접한 지역으로 움직일 수 있는 경우는 (1) 평지로 이동할 경우, (2) 내려갈 경우, (3) 올라갈 경우의 세 가지이다.
이 세가지 경우에 필요한 "힘"의 양은 다음과 같이 표현될 수 있다.
(1) 인접한 같은 높이의 지역을 수평 이동할 경우에는 그냥 평지를 걸어가면 되므로 힘이 전혀 들지 않는다고 가정한다.
예를 들면 Mount[5,2]에서 Mount[5,3]으로 이동하는 경우와 Mount[4,5]에서 Mount[5,5]로 이동하는 경우에는 전혀 힘이 들지 않는다.
(2) 내리막길을 따라갈 경우(예를 들면, Mount[2,3]에서 Mount[2,2]로 갈 때)에는 그 높이 차이 만큼의 힘이 든다.
즉 이 경우에는 5-3=2만큼의 힘이 든다.
(3) 오르막길을 오를 경우에는 이동할 두 지역의 높이 차의 제곱 만큼의 힘이 든다.
즉 Mount[1,2]에서 Mount[1,3]으로 갈 경우는 (4-2)^2=4 만큼의 힘이 든다.
입력
첫 줄에는 산의 크기인 Mount[N, N]의 N값이 주어지고, 두 번째 줄에는 정상의 위치 Mount[i,j]의 i, j값이 주어진다.
단, Mount[N, N]에서 N은 100 이하이고, 각 지형의 최대 높이는 50 이하라고 가정한다.
그 다음 N개의 줄은 산의 크기에 따른 각 지점의 높이가 양의 정수 값으로 주어진다.
출력
첫째 줄에 정상까지 도달하는 가장 경제적인 경로를 따라 올라가는데 사용된 힘을 출력한다.
예제1
5
3 3
1 2 4 3 2
1 3 5 4 4
2 3 6 5 1
3 1 4 1 3
2 3 3 5 3
8