{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e你喜欢寻宝吗?今天,iSea 和他的一个朋友又开始了一次冒险之旅。正如大多数电影所说,他们在旅途中发现了许多藏在地下的黄金。\u003cbr\u003e现在,iSea 聪明的朋友已经得到了他们即将寻宝地点的地图,简化后的地图有三种地面类型:\u003cbr\u003e\u003cbr\u003e● \u0027.\u0027 代表空地,可以通过\u003cbr\u003e● \u0027#\u0027 代表障碍物,无法通过\u003cbr\u003e● \u0027*\u0027 代表藏有黄金的地面,同样可以通过(但你不会去,对吧?)\u003cbr\u003e\u003cbr\u003eiSea 非常高兴的是,他的朋友是一个非常正直的人,他不会拿走不属于他的东西,所以所有的宝藏都属于 iSea 自己!\u003cbr\u003e但他的朋友有一个要求,他会在地图上设置若干个集结点,即 \u0027A\u0027, \u0027B\u0027 ... \u0027Z\u0027, \u0027a\u0027, \u0027b\u0027 ... \u0027z\u0027(按顺序排列,但可能少于 52 个),他们从 \u0027A\u0027 开始,每次朋友到达下一个集结点的最短路径处,他们必须在这里汇合(即 iSea 比他的朋友更早或者同时到达),然后一起出发,但你可以选择不同的路径。最初,iSea 的速度和他的朋友是一样的,但为了抢夺宝藏,他在每段路程中节省一个时间单位,他只用一个单位来获取一个宝藏,获取后,宝藏的位置变为空地。\u003cbr\u003e在他朋友的规则下,iSea 最多能获取多少宝藏?\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入中包含多个测试用例。\u003cbr\u003e\u003cbr\u003e每个测试用例以两个整数 R, C(2 ≤ R, C ≤ 100)开头,表示行数和列数。\u003cbr\u003e然后是 R 个字符串,每个字符串包含 C 个字符(必须是 \u0027A\u0027 – \u0027Z\u0027 或 \u0027a\u0027 – \u0027z\u0027 或 \u0027.\u0027 或 \u0027#\u0027 或 \u0027*\u0027),表示坐标中的类型。\u003cbr\u003e\u003cbr\u003e输入以文件结束符结束。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一个整数,表示 iSea 最多能获取的黄金数量,如果他们无法在一个或多个集结点相遇,则输出 -1。\u003cbr\u003e\u003cbr\u003e"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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 4\r\nA.B.\r\n***C\r\n2 4\r\nA#B.\r\n***C\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}