#P4978. 疲劳的邮递员

疲劳的邮递员

题目背景

乐乐在一个山中小镇里得到了一个邮递员的差事。这个小镇可以用一个 n×nn \times n 的矩阵表示。每个区域有三种状态:用 K\texttt{K} 表示房屋,用 P\texttt{P} 表示邮局或用 .\texttt{.} 表示牧场。此外,每个区域被分配一个高度。

每天早晨,乐乐都给镇上的每户人家送邮件。他从用 P\texttt{P} 表示的区域开始。乐乐只能水平、垂直或斜向移动到相邻的区域。他一旦送完最后一封邮件,就必须返回邮局。

乐乐不知道他的工作会有多疲劳。令乐乐在投递邮件时所到的最高处和最低处的高度之差等于他的疲劳度。帮他找出疲劳度最小的方式,让乐乐投递所有的邮件。

题目描述

给定一个 n×nn \times n 的矩阵。

每个位置可能有 K\texttt{K} P\texttt{P} .\texttt{.} 三种可能状态,此外还有一个高度 hi,jh_{i,j}

你需要从状态为 P\texttt{P} 的位置开始,水平、垂直或斜向移动,经过所有状态为 K\texttt{K} 的位置,最终回到起点。

在这路程中,你需要让经过的位置的 maxhminhmax_h-min_h 最小化。

请你求出最小化的值。

输入文件 postar.in

第一行包含一个整数 nn

下面的 nn 行每行 nn 个字符表示矩阵。

下面的 nn 行每行 nn 个正整数,表示区域高度。

输出文件 postar.out

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

2
P.
.K
2 1
3 2
0

从邮局开始,乐乐可以直接移动到房屋,然后再回到邮局。因为这两个区域高度相同,所以乐乐的疲劳等于 00

3
P..
.KK
...
3 2 4
7 4 2
2 3 1
2
3
K.P
...
K.K
3 3 4
9 5 9
8 3 7
5

提示

对于矩阵,其中 P\texttt{P} 将正好出现一次,而 K\texttt{K} 将至少出现一次。

对于 100%100\% 的数据 2n502 \le n \le 50