2514: 蒜头君救人
Memory Limit：512 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：1
Solved：1
Description
蒜头君是一个乐于助人的好孩子，这天他所在的乡村发生了洪水，有多名村民被困于孤岛上，于是蒜头君决定去背他们离开困境，假设蒜头君所在的村子是 n×m 的网格，网格中.号代表平地，#号代表该地已被洪水淹没，A、B……等大写字母表示该地有村民被困，s代表蒜头君的起点，t代表蒜头君的终点。
蒜头君的初始速度为 kkk 秒一格，他每次可以向上下左右 4 个方向中的一个移动 1 格。在背上一个村民后，他的速度可能会降低，也可能会加快，但他的速度不能快于 1 秒每格，那么蒜头君想知道，他最快需要多长时间将所有村民救出？
注意：不能在终点以外的地方放下村民；可以同时背多个村民。
Input
第一行 3 个正整数 n,m,k，分别表示村庄长度、宽度、蒜头君初始速度。
接下来 n 行，每行一个长度为 m 的字符串，表示村庄的地形，字符串意义如上所述。
接下来若干行，每行一个大写字母、一个整数，表示该编号的村民会使 k 增加 / 减少多少。行数等同于地形中大写字母的个数。大写字母按字典序，即A、B、C的顺序排列，保证前后两行的字母是连续的。
Output
输出 1 个整数，表示最小用时。
Sample Input Copy
4 4 2
s.##
..A#
.B##
...t
A -3
B 4Sample Output Copy
17HINT
对于 10% 的数据，满足 1≤n,m≤5，村民个数为 1；
对于 50% 的数据，满足 1≤n,m≤5，村民个数小于等于 5；
对于 100% 的数据，满足 1≤n,m≤10，村民个数小于等于 10。