P6705 [COCI 2010/2011 #7] POŠTAR

Mirko 在一个山中小镇里得到了一个邮递员的差事。这个小镇可以用一个 $n \times n$ 的矩阵表示。每个区域有三种状态：用 $\texttt{K}$ 表示房屋，用 $\texttt{P}$ 表示邮局或用 $\texttt{.}$ 表示牧场。此外，每个区域被分配一个高度。 每天早晨，Mirko 都给镇上的每户人家送邮件。他从用 $\texttt{P}$ 表示的区域开始。Mirko 只能水平、垂直或斜向移动到相邻的区域。他一旦送完最后一封邮件，就必须返回邮局。 Mirko 不知道他的工作会有多无聊。令 Mirko 在投递邮件时所到的最高处和最低处的高度之差等于他的疲劳度。帮他找出疲劳度最小的方式，让 Mirko 投递所有的邮件。

给定一个 $n \times n$ 的矩阵。 每个位置可能有 $\texttt{K}$ $\texttt{P}$ $\texttt{.}$ 三种可能状态，此外还有一个高度 $h_{i,j}$。 你需要从状态为 $\texttt{P}$ 的位置开始，水平、垂直或斜向移动，经过所有状态为 $\texttt{K}$ 的位置，最终回到起点。 在这路程中，你需要让经过的位置的 $max_h-min_h$ 最小化。 请你求出最小化的值。

第一行包含一个整数 $n$。 下面的 $n$ 行每行 $n$ 个字符表示矩阵。 下面的 $n$ 行每行 $n$ 个正整数，表示区域高度。

一个非负整数表示最小疲劳度。

#### 样例 1 解释 从邮局开始，Mirko 可以直接移动到房屋，然后再回到邮局。因为这两个区域高度相同，所以 Mirko的疲劳等于 $0$。 #### 数据规模及约定 对于矩阵，其中 $\texttt{P}$ 将正好出现一次，而 $\texttt{K}$ 将至少出现一次。 对于 $100\%$ 的数据 $2 \le n \le 50$ #### 说明 本题满分 $100$ 分。 译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #7](https://hsin.hr/coci/archive/2010_2011/contest7_tasks.pdf) T4 POŠTAR