관측 장비 순회

한 연구소가 산지 곳곳에 관측 장비를 설치해 두었다. 이 산지는 N × N 크기의 격자로 나뉘어 있고, 각 칸에는 그 칸의 고도가 적혀 있다.

격자에는 다음의 세 가지 표시가 쓰인다.

(1) P는 드론 격납고가 있는 칸이다. 격자 전체에 정확히 하나 있다. (2) K는 배터리를 갈아 주어야 하는 관측 장비가 있는 칸이다. 하나 이상 있다. (3) 점(.)은 아무것도 없는 빈 칸이다.

드론은 격납고에서 출발하여 모든 관측 장비 칸을 한 번 이상 지난 뒤에 다시 격납고로 돌아와야 한다. 드론은 현재 칸에서 가로, 세로, 대각선으로 맞닿은 여덟 칸 가운데 어디로든 한 번에 옮겨 갈 수 있다. 같은 칸을 여러 번 지나도 된다.

그런데 이 드론은 기압이 급하게 바뀌면 고장이 난다. 그래서 드론이 지나는 칸들 가운데 가장 높은 칸의 고도와 가장 낮은 칸의 고도의 차이를 되도록 작게 만들고 싶다. 출발 지점인 격납고 칸의 고도도 지나는 칸에 들어간다.

산지의 표시와 각 칸의 고도가 주어졌을 때, 드론이 격납고에서 출발해 모든 관측 장비를 거쳐 격납고로 돌아올 수 있는 경로 가운데, 지나는 칸의 최고 고도와 최저 고도의 차이가 가장 작은 값을 계산하는 프로그램을 작성하여라.

예를 들어 N=4인 산지의 표시가 다음의 표와 같다고 해보자.

또한 각 칸의 고도는 다음의 표와 같다고 해보자.

격납고는 2행 2열에 있고 고도는 20이다. 관측 장비는 1행 4열에 고도 35, 2행 1열에 고도 25, 4행 2열에 고도 30으로 세 대가 있다.

드론이 고도가 17 이상 35 이하인 칸만 밟는다고 해보자. 밟을 수 있는 칸을 ○로 표시하면 다음의 표와 같다.

격납고인 2행 2열에서 출발하면 2행 1열과 3행 3열로 갈 수 있고, 3행 3열에서 다시 4행 2열, 4행 3열, 2행 4열로 갈 수 있다. 2행 4열에서 1행 4열까지 닿는다. 그래서 세 관측 장비를 모두 거친 뒤에 격납고로 돌아올 수 있다. 이때 고도의 차이는 35 - 17 = 18이다.

고도의 범위를 18보다 좁게 잡으면 세 관측 장비 가운데 하나라도 닿지 못한다. 따라서 이 경우의 정답은 18이다.

입출력 예시

예시 1

입력

4
...K
KP..
....
.K..
45 50 2 35
25 20 2 29
2 47 17 41
13 30 22 38

출력

18

예시 2

입력

2
P.
K.
5 1
38 42

출력

33

예시 3

입력

5
KKKKK
KKKKK
KKKPK
KKKKK
KKKKK
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

출력

0