{"trustable":true,"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\u003eThe First Universal Bank of Denview has just been robbed!\n You want to catch the robbers before they leave the state.\u003c/p\u003e\n \u003cp\u003eThe state of Calirado can be represented by a rectangular\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e-by-\u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e grid of characters, with the\n character in each grid cell denoting a terrain type. The\n robbers begin within the cell marked ‘\u003ctt class\u003d\"tt\"\u003eB\u003c/tt\u003e’,\n indicating the Bank of Denview. They will then travel across\n the state by moving from grid cell to grid cell in the four\n cardinal directions (left, right, up, down). (Note that the\n robbers pass only through grid edges, and not corners.) If the\n robbers manage to leave the state (by crossing any boundary\n edge of the grid) they will go into hiding, never to be seen\n again. You must stop this.\u003c/p\u003e\n \u003cp\u003eTo catch the robbers, you can set up barricades. Barricades\n are placed inside a grid cell, and prevent the robbers from\n traveling into the cell (from any direction). Each grid square\n consists of a different type of terrain, with different cost\n for placing a barricade. You cannot place a barricade on the\n bank (‘\u003ctt class\u003d\"tt\"\u003eB\u003c/tt\u003e’) or on any cell containing a dot\n (‘\u003ctt class\u003d\"tt\"\u003e.\u003c/tt\u003e’), though the robbers can travel freely\n through these cells. Every other cell will contain a lowercase\n English letter, indicating a terrain type.\u003c/p\u003e\n \u003cp\u003eFind the cheapest way to prevent the robbers from escaping\n Calirado.\u003c/p\u003e\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 grid representing\n Calirado, and the number of different terrain types. 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 Calirado. 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. Calirado is guaranteed to contain exactly\n one bank. After the grid, 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 barricade on a grid cell of\n each terrain type. \u003cspan class\u003d\"tex2jax_process\"\u003e$c_1$\u003c/span\u003e\n is the cost for terrain 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 barricades\n that you need to place to prevent the robbers 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 barricade 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 bank is on the border,\n there is no way to prevent the robbers from escaping the\n state.\u003c/p\u003e\n \u003cp\u003eIn the third example, we must prevent the robbers from\n leaving the bank 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 barricade in each of the three\n 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 "}}]}