梅花桩
暂无测试数据。
Description
森林王国的中央游乐园里,有一个 \(n \cdot n\) 的矩阵形式的梅花桩。每个梅花桩都有自己的高度 \(h\),有些梅花桩上有松鼠最喜欢吃的松果。现在松鼠 \(\text{Scarral}\) 目前站在其中一根梅花桩上,它想吃掉所有的松果,\(\text{Scarral}\) 能从当前所在位置向它周围 \(8\) 个相邻的位置跳跃,如果我们定义郁闷值为 \(\text{Scarral}\) 在吃松果过程中所经过的最高处和最低处高度之差,那么\(\text{Scarral}\)的郁闷值最低是多少。
Input
输入分为 \(3\) 个部分
第 \(1\) 行是一个整数 \(n\),表示 \(n\cdot n\) 矩阵。
接下来是一个 \(n\cdot n\) 的矩阵,每个位置可能是 K
、P
或者 .
。K
表示这棵梅花桩上有松果,P
表示松鼠开始的位置,.
表示这个梅花桩上没有松果。
接下来又是一个 \(n\cdot n\) 的矩阵,每个位置表示该位置上梅花桩的高度。
Output
输出一行一个整数,表示最小的郁闷值。
Sample
Sample input
#1
2
P.
.K
2 1
3 2
#2
3
P..
.KK
...
3 2 4
7 4 2
2 3 1
#3
3
K.P
...
K.K
3 3 4
9 5 9
8 3 7
Sample output
#1
0
#2
2
#3
5
Hint
注意:至少会有一个松果。
对于 \(30\%\) 的数据 \(n\le 10,\ h\le 100\);
对于 \(60\%\) 的数据 \(n\le 50,\ h\le 100\);
对于 \(100\%\) 的数据 \(1\le n\le 50,\ 1<h\le 1000\)。