COCI2010-2011#7 邮递员 - 最小疲劳度路线规划

COCI2010-2011#7 邮递员 - 最小疲劳度路线规划

Mirko 在一个山中小镇里得到了一个邮递员的差事。这个小镇可以用一个 'n x n' 的矩阵表示。每个区域有三种状态：用 'K' 表示房屋，用 'P' 表示邮局或用 '.' 表示牧场。此外，每个区域被分配一个高度。

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

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

问题描述

给定一个 'n x n' 的矩阵。

每个位置可能有 'K', 'P', '.' 三种可能状态，此外还有一个高度 'h_{i,j}'。

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

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

请你求出最小化的值。

输入格式

第一行包含一个整数 'n'。

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

下面的 'n' 行每行 'n' 个正整数，表示区域高度。

输出格式

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

样例 #1

样例输入 #1

2
P.
.K
2 1
3 2

样例输出 #1

0

样例 #2

样例输入 #2

3
P..
.KK
...
3 2 4
7 4 2
2 3 1

样例输出 #2

2

样例 #3

样例输入 #3

3
K.P
...
K.K
3 3 4
9 5 9
8 3 7

样例输出 #3

5

提示

样例 1 解释

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

数据规模及约定

对于矩阵，其中 'P' 将正好出现一次，而 'K' 将至少出现一次。

对于 100% 的数据 2 ≤ n ≤ 50

说明

本题满分 100 分。

Test Input Reasoning:

本题相对简单，我们先从最简单的情况开始分析。

考虑一个 2 x 2 的矩阵，其中邮局在左上角，房屋在右下角。

P.
.K

此时，邮局只需要直接到达房屋即可完成任务，疲劳度为 0。