解题思路

1. 预处理两点间最短距离：

   • 使用 BFS 计算网格中任意两点之间的最短路径，特别是从每个金矿到其他金矿的最短路径以及从起点到各个金矿的最短路径。

2. 枚举所有金矿的采集顺序：

   • 由于金矿的数量最多为 5，因此可以枚举所有金矿的采集顺序。每个采集顺序是合法的，只要每个金矿在前一个金矿之后被访问即可。

题目内容

在《无主星渊》的太空战场中，玩家需操控飞船从起点$(S)$出发，在$n×m$的网格中以最短时间采集所有的金矿。飞船每次仅能向上下左右四个方向移动一个网格，金矿可以以任何先后顺序被采集，飞船到达金矿后可以选择立即采集也可以选择路过。

一共有$k$个金矿，金矿初始的矿产值为$Xi$，当飞船采集到第$a(1<=a<=k)$个金矿后，每移动一步，所有未被采集的金矿都会减少$a$点矿产值，当金矿的矿产值减少到$1$的时候将不再减小。

需要你帮玩家算一下，玩家最多可以采集到金矿的总价值。

网格包含以下元素:

#:不可穿越的障碍物

.：可自由航行的太空区域

$1$~$5$: 表示k个金矿的编号

$S$: 飞船起点

输入描述

首行: $n\ m\ k(1≤n,m≤50,1≤k≤5)$

后续$n$行，每行$m$个字符表示$n*m$的网格的信息。

最后一行是$k$个整数，第$i$个数表示编号为$i(1<=i<=k)$的金矿的初始矿产值$Xi (1<= Xi <=1000)$。

输出描述

玩家最多可以采集到的金矿总矿产值，数据保证所有金矿都可以到达。

样例1

输入

5 7 3
S.....3
##.....
..##...
..1....
2..#...
10 20 30

输出

41

样例2

输入

4 4 1
....
.##.
.##.
S##1
100

输出

100

样例3

输入

5 7 3
S.....3
##.....
..##...
..1....
2..#...
40 1 1

输出

42