/*문제 설명
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[y, x]의 y, x값이 주어진다.
단, Mount[n, n]에서 n은 100이하이고, 각 지형의 최대 높이는 50이하라고 가정한다.
그 다음 n개의 줄은 산의 크기에 따른 각 지점의 높이가 양의 정수 값으로 주어진다.
출력
첫째 줄에 정상까지 도달하는 가장 경제적인 경로를 따라 올라가는데 사용된 힘을 출력한다.
입력 예시
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
도움말
경로는 다음과 같다.
2[1, 5]->3[1, 4]->4[2, 4]->5[3, 4]->6[3, 3]
= 2 * 2 + 1 * 1 + 1 * 1 + 1 * 1 + 1 * 1
= 8
*/
#include<stdio.h>
/*
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
*/
int N;
int GARO, SERO;
int map[102][102];
int chk[102][102];
typedef struct {
int posY;
int posX;
} _pos;
_pos POSITION[1000000];
void main()
{
int i, j;
scanf("%d", &N);
scanf("%d %d", &SERO, &GARO);
for (i = 1; i <= N; i++)
{
for (j = 1; j <= N; j++)
{
scanf("%d", &map[i][j]);
}
}
for (i = 1; i <= N; i++)
{
for (j = 1; j <= N; j++)
{
chk[i][j] = 0x7fffffff;
}
}
int head = 0, tail = 0;
for (i = 0; i <= N +1; i++)
{
for (j = 0; j <= N +1; j++)
{
if (chk[i][j] == 0)
{
POSITION[tail].posY = i;
POSITION[tail].posX = j;
tail++;
}
}
}
int Dy[] = { -1, 1, 0, 0 };
int Dx[] = { 0, 0, -1, 1 };
int temp;
while (1)
{
if (head == tail) break;
for (int dir = 0; dir < 4; dir++)
{
int tmpY = POSITION[head].posY + Dy[dir];
int tmpX = POSITION[head].posX + Dx[dir];
if (tmpY >= 1 && tmpX >= 1 && tmpY <= N && tmpX <= N)
{
temp = map[POSITION[head].posY][POSITION[head].posX] - map[tmpY][tmpX];
if (temp < 0) temp = temp * temp;
temp += chk[POSITION[head].posY][POSITION[head].posX];
if (chk[tmpY][tmpX] > temp)
{
chk[tmpY][tmpX] = temp;
POSITION[tail].posY = tmpY;
POSITION[tail].posX = tmpX;
tail++;
}
}
}
head++;
}
printf("%d", chk[SERO][GARO]);
}