P3354.第3题-金矿价值
题目内容
在《无主星渊》的太空战场中，玩家需操控飞船从起点(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
