{"trustable":false,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eGiven a $n$ by $m$ rectangle grids. There is a bad guy at position \u0027B\u0027, and he can move across the state from one grid cell to another along the four cardinal directions (left, right, up, and down) every time. You can put some roadblocks on the grid consisting of lowercase letters, and each lowercase letter has a different cost. Find the cheapest way to trap the bad guy. Keep him from leaving this rectangle.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line contains three integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e, and \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le n, m \\le 30$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le c\n \\le 26$\u003c/span\u003e): the dimensions of the grids, and the number of different roadblocks. Then\n follows \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e lines of\n exactly \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e characters\n each: the map of the bad guy. Each character is either ‘\u003ctt class\u003d\"tt\"\u003eB\u003c/tt\u003e’, ‘\u003ctt class\u003d\"tt\"\u003e.\u003c/tt\u003e’, or one of the first\n \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e lowercase letters of\n the English alphabet. It is guaranteed to contain exactly one\n ‘\u003ctt class\u003d\"tt\"\u003eB\u003c/tt\u003e’. After the grids, there is a line containing\n \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e space-separated\n integers \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq c_ i \\leq 100\\,\n 000$\u003c/span\u003e, the costs of placing a roadblock on a grid cell of\n each type of roadblock. \u003cspan class\u003d\"tex2jax_process\"\u003e$c_1$\u003c/span\u003e\n is the cost for roadblock type ‘\u003ctt class\u003d\"tt\"\u003ea\u003c/tt\u003e’,\n \u003cspan class\u003d\"tex2jax_process\"\u003e$c_2$\u003c/span\u003e is the cost for\n ‘\u003ctt class\u003d\"tt\"\u003eb\u003c/tt\u003e’, and so forth.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003ePrint one integer, the minimum total cost of the roadblocks\n that you need to place to prevent the bad guy from escaping. If\n there is no way to prevent the robbers from escaping, print\n \u003ctt class\u003d\"tt\"\u003e-1\u003c/tt\u003e instead.\u003c/p\u003e\n \u003cp\u003eIn the first example, the minimum cost is to block the\n central three squares on each side of the bank for a total cost\n of \u003cspan class\u003d\"tex2jax_process\"\u003e$12$\u003c/span\u003e.\u003c/p\u003e\n \u003cp\u003eIn the second example, since the start place is on the border,\n there is no way to prevent the bad guy from escaping the\n state.\u003c/p\u003e\n \u003cp\u003eIn the third example, we must prevent the bad guy from\n leaving to the top, bottom, and right, or else we\n cannot prevent them from leaving the state. To the left,\n however, it is cheaper to allow passage through the ‘\u003ctt class\u003d\"tt\"\u003eb\u003c/tt\u003e’ cell, and then roadblocks in each of the three directions from there. The total cost is \u003cspan class\u003d\"tex2jax_process\"\u003e$7 + 5 + 7 + 3(1) \u003d 22$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 5 1\naaaaa\na...a\na.B.a\na...a\naaaaa\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e12\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 2 1\naB\naa\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 3\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 3 3\n.abc\nabBc\n.abc\n1 7 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e22\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}