317010 - 采矿

【题目描述】17.10 采矿（mining）jisuanke 16444

有一个人在n×m的字符网格中采矿，“.”代表平地，“#”代表障碍，“s”代表出发点，“t”代表终点，英文大写字母表示该处有矿产（矿产数不超过10）。

假设他的初始速度为k秒一格，他每次可以向上、下、左、右4个方向中的一个位置移动1格。在带上一处矿产后，他的速度可能会降低，也可能会加快，但不会快于1秒每格，试问最快需要多长时间将所有矿产取走？ 注意：不能在终点以外的地方放下矿产，可以同时带多处矿产。

输入第一行3个正整数n，m，k（1≤n，m≤10），分别表示网格的长度、宽度和人的初始速度。 接下来n行，每行一个长度为m的字符串描述网格。 随后若干行，每行一个大写字母、一个整数，表示该编号的矿产会使速度增加或减少多少。 行数等同于地形中大写字母的个数。大写字母按字典序，即A、B、C的顺序排列，保证前后两行的字母是连续的。

输出1个整数，表示最小用时。