1405: 投掷炸弹
内存限制：128 MB
时间限制：1.000 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：2
通过：1
题目描述
小彬在玩一款战争游戏，游戏中小彬接到一个轰炸敌方兵营的任务。这个兵营由一个 m 行 n 列的矩阵表示，矩阵里面有敌军士兵的位置，还有可投掷炸弹的地点（只有炸弹投在这些地点才能消灭敌兵）。另外还有急救站，急救站分为三个等级，分别能救治一个、两个、三个士兵。由于敌人的防空系统非常厉害，所以这次轰炸任务只有一次投弹机会。炸弹具有一定的爆炸力，用整数 k 表示。炸弹的杀伤范围是以投弹点为中心向周围各延伸 k 个格的矩形区域。
请你编写程序帮助小彬计算出炸弹能消灭敌人的最大数量。
小彬能获得的信息包括：地图的尺寸，敌方兵营内士兵、投弹点和急救站的信息，还有炸弹的爆炸力。敌方兵营示意图如下所示。
输入格式
m+1 行
第一行 3 个正整数 m、n、k，分别表示兵营矩阵的行数、列数和炸弹的爆炸力，三个整数之间用空格隔开。
接下来是 m 行，每行是一个长度为 n 的字符串，字符串内包含 0、1、a、b 和 c，其中 0 表示此位置可投放炸弹，1 表示此位置是 1 个士兵，a 表示能救治 1 个士兵的急救站，b 表示能救治 2 个士兵的急救站，c 表示能救治 3 个士兵的急救站。
输出格式
一个整数，代表最多能消灭的士兵数量。
输入样例 复制
4 5 2
11011
10b11
1111a
011c0输出样例 复制
8数据范围与提示
样例解释：
样例是一个 4×5 的矩阵，k=2 是炸弹的爆炸力，表示以投弹点为中心向周围辐射 2个格的矩形区域。
最多能消灭敌人的方案是将炸弹投放到矩阵的第 1 行第 3 列，炸弹的横向辐射范围是 1~5，纵向辐射范围是 1~3，此范围有 11 个士兵，由于第 2 和第 3 行各有一个 a 和 b可救治 3 人，所以可消灭 8 人。
数据规模：
共 10 个测试数据，其中：
40%的数据满足：3≤n≤80，3≤m≤80，1≤k≤15
80%的数据满足：3≤n≤800，3≤m≤800，1≤k≤300
100%的数据满足：3≤n≤1000，3≤m≤1000，1≤k≤400