문제
주웅이는 언덕에 있는 작은 도시의 우편배달부이다. 이 도시는 N*N 배열 형태이다. 배열의 각 번지에는 우체국을 나타내는 'P'나 집을 나타내는 'K', 또는 다닐수 있는 초원을 나타내는 '.' 이 들어가있다. 같은 크기의 배열을 하나 더 입력받는데 여기에는 각 번지의 고도(높이)에 대한 정보가 들어가 있다.
주웅이는 매일 아침 모든 집에 우편물을 배달한다. 그는 마을에서 하나뿐인 우체국 'P'에서 출발하여 수평, 수직 또는 대각선으로 이동하여 모든 집에 우편물을 배달한다. 마지막집까지 배달을 마치면 우체국으로 돌아와야 한다.
이렇게 매일 우편을 배달하는 일은 각 주소의 고도(높이)가 달라, 주웅이에게는 성가시고 힘든일이다. 힘든 정도는 주웅이가 배달하는 동안 방문하는 모든 우체국, 집, 초원의 최대고도(높이)와 최소고도(높이)의 차이다.
주웅이의 힘든 정도를 구하여 출력하는 프로그램을 작성하시오.
입력
첫 행에 마을의 크기 N(1≤N≤50)이 입력된다.
다음 N행 N열에 걸쳐 공백없이 마을의 정보가 입력된다. 우체국을 나타내는 'P'는 오직 한번만 나온다. 집을 나타내는 'K'는 적어도 한번 이상 나온다.
다음 N행 N열에 걸쳐 고도(높이)를 나타내는 값이 공백으로 구분하여 1,000,000 이하의 정수들로 입력된다.
출력
주웅이의 힘든 정도를 구하여 출력하시오.
예제1
입력
2
P.
.K
21
32
출력
0
힌트
출처
COCI 2010/2011 contest#7