问题 B: 3.陷阱 (trap)

问题 B: 3.陷阱 (trap)

题目描述

  给定一个 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。

输出

输出共一行,表示 到达终点最后最多剩下多少血。 如果不能到终点,则输出-1。

样例输入输出

输入#1 复制
5 5 2 15
1 1 5 4
....A
####.
.....
###B#
.....
9
3
输出#1 复制
3
输入#2 复制
5 5 2 10
1 1 5 4
....A
####.
.....
###B#
.....
9
3
输出#2 复制
-1

提示

【数据范围】
对 30%的数据,n<10, m<10, k=0。
对 70%的数据,n<10, m<10, k<10。
对 100%的数据,n≤100,m≤100, k≤26。
注意:起点和终点都是给定的

序号 标题 作者 发表时间 费用 订购数 操作