问题 AV: 陷阱
内存限制：128 MB
时间限制：1 S
题面：传统
评测方式：文本比较
上传者：
提交：85
通过：28
题目描述
给定一个n*m的网格地图，格子有三种情况：1. '.' 表示空，可以正常通行2. '#'表示有墙，不能通行
3.大写英文字母（A～Z）表示有陷阱，可以通行，但经过会扣一定的血量，并且不会消失
一共有k个陷阱（编号从A开始，ABCDE.），k<=26，并日给定起点，终点，和初始血量H.行走方向只有上下左右四个方向，注意在行走过程中不能有任意时刻的血量小于等于0。输出到达终点的最大血量。
输入格式
一共有 n+k+2 行，
第一行依次为 n, m, k, H。 其中 n≤100， m≤100, k≤26, H≤200。
第二行四个整数， 表示起点的行、 列坐标和终点的行、 列坐标。 棋盘从左往右依次是 1…m 列， 从上倒下依次是 1…n 行。 数据保证起点和终点所在的格子都是空的。
接下来 n 行， 每行一个长度为 m 的字符串， 表示棋盘的情况。 .表示为空， #表示为墙， A-Z 的字符表示陷阱的种类。
接下来 k 行
接下来的第 1 行， 一个数表示 A 代表的陷阱扣多少血；
接下来的第 2 行， 一个数表示 B 代表的陷阱扣多少血；
……
接下来的第 k 行...
以此类推， 扣的血量小于等于 200。
第一行依次为 n, m, k, H。 其中 n≤100， m≤100, k≤26, H≤200。
第二行四个整数， 表示起点的行、 列坐标和终点的行、 列坐标。 棋盘从左往右依次是 1…m 列， 从上倒下依次是 1…n 行。 数据保证起点和终点所在的格子都是空的。
接下来 n 行， 每行一个长度为 m 的字符串， 表示棋盘的情况。 .表示为空， #表示为墙， A-Z 的字符表示陷阱的种类。
接下来 k 行
接下来的第 1 行， 一个数表示 A 代表的陷阱扣多少血；
接下来的第 2 行， 一个数表示 B 代表的陷阱扣多少血；
……
接下来的第 k 行...
以此类推， 扣的血量小于等于 200。
输出格式
共一行， 表示到达终点最后最多剩下多少血。 如果不能到终点， 则输出-1。
输入样例 复制
5 5 2 15
1 1 5 4
....A
####.
.....
###B#
.....
9
3输出样例 复制
3数据范围与提示
【样例2输入】
【样例2输出】
-1
【数据规模】
对 30%的数据， n<10, m<10, k=0。
对 70%的数据， n<10, m<10, k<10。
对 100%的数据， n≤100， m≤100, k≤26。
注意： 起点和终点都是给定的
|
5 5 2 10 1 1 5 4 ....A ####. ..... ###B# ..... 9 3 |
-1
【数据规模】
对 30%的数据， n<10, m<10, k=0。
对 70%的数据， n<10, m<10, k<10。
对 100%的数据， n≤100， m≤100, k≤26。
注意： 起点和终点都是给定的