{"trustable":false,"sections":[{"title":"题面描述:","value":{"format":"MD","content":"长春第一国际银行刚刚被抢劫了!!!你想要在劫匪离开吉林省之前抓住他们\n\n吉林的形状是一个 m 行 n 列的方格图。劫匪们逃离吉林,他们只能在方格图上东、西、南、北四个方向移动,当他们到达方格图的边界,他们就成功的逃离了吉林。\n\n你可以在方格上设置障碍,使得他们无法移动到某个特定方格。然而,根据地形的不同,设置障碍的花费也不同,有些地形甚至不能设置障碍。\n\n你的目的是,寻找一种花费最小方式,使得劫匪无法逃离吉林。"}},{"title":"输入:","value":{"format":"MD","content":"输入的第一行有三个空格隔开的数字 n, m 和 c (1 \u003c\u003d n, m \u003c\u003d 30, 并且 1 \u003c\u003d c \u003c\u003d 26)\n\nm 为方格图的行数, n 为方格图的列数, 并且 c 是吉林地形的种类数。(注意 n、 m 的含义以及读入顺序!)\n\n接下来的 m 行,每一行包含 n 个字母,表示该位置的地形:\n\n - 大写字母 \u0027B\u0027 表示是银行的位置, 也是劫匪最开始的位置。\n\n - 小写字母 \u0027a\u0027 ~ \u0027z\u0027 表示不同的地形。 只有前 c 个字母会出现在方格图中(若 c \u003d 2, 则地图中只会出现小写字母 \u0027a\u0027 和 小写字母 \u0027b\u0027 )\n\n - 一个点 (\u0027.\u0027) 表示该方格不能被放置障碍。\n\n保证图中一定包含且仅包含一个大写字母 \u0027B\u0027\n\n输入的最后一行,包含 c 个空格隔开的数字 x1, x2 ... xc(1 \u003c\u003d xi \u003c\u003d 100,000),表示在地形为 \u0027a\u0027, \u0027b\u0027 ... 的方格上布置障碍的花费。"}},{"title":"输出:","value":{"format":"MD","content":"输出使得劫匪无法逃离吉林的最小花费。\n\n如果无法阻碍劫匪逃出吉林,就输出 -1"}},{"title":"样例 1 输入:","value":{"format":"MD","content":"5 5 1\naaaaa\na...a\na.B.a\na...a\naaaaa\n1"}},{"title":"样例 1 输出:","value":{"format":"MD","content":"12"}},{"title":"样例 1 解释:","value":{"format":"MD","content":"aXXXa\nX...X\nX.B.X\nX...X\naXXXa\n\n在标为 X 的方格上设置障碍,总花费为 12 * 1 \u003d 12"}},{"title":"样例 2 输入:","value":{"format":"MD","content":"2 2 1\naB\naa\n1"}},{"title":"样例 2 输出:","value":{"format":"MD","content":"-1\n"}},{"title":"样例 2 解释:","value":{"format":"MD","content":"由于银行在地图边界上,而且我们不能再银行上设置障碍,所以我们无法阻止劫匪逃出吉林"}}]}