New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

2010: 拦截小偷

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：52 通过：6
提交提交记录统计

题目描述

在m*n的地图上，有一个小偷可以上下左右向四个方向移动，当他走出地图范围算他逃跑成功
存在c种障碍物，地图上存在一些点可以放置指定的障碍物，但是放置障碍物需要一些花费
求最小的花费使得小偷不能逃跑成功

输入格式

输入第一行为包含三个整数$n,m,c(1<=n,m<=30,1<=c<=26)
n,m表示地图的范围，c表示障碍物的种数
接下来存在m行，每行n个字符表示地图
  • 'B'表示小偷起点位置，输入保证只存在一个起点位置
  • 'a'-'z'表示该位置可以放的障碍物的种类，输入保证地图中只会出现只有前c个小写字母
  • '.'表示该位置为空
接下来一行存在c个整数，分别表示前c个小写字母代表的障碍物的花费

输出格式

如果不能阻止小偷逃跑，输出"-1"。否则输出最小的花费

输入样例 复制 

5 5 1
aaaaa
a...a
a.B.a
a...a
aaaaa
1

输出样例 复制 

12