{"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 哈利: “但是海格,我要怎么支付这一切?我没有钱。” \u003cbr\u003e 海格: “哈利,你的钱在那里!古灵阁,巫师银行!没有比这更安全的地方了。除了霍格沃茨也许。” \u003cbr\u003e —— 鲁伯斯·海格对哈利·波特说。\u003cbr\u003e\u0026nbsp;\u0026nbsp;古灵阁巫师银行是巫师世界唯一的银行,由妖精所有和经营。它是由一个名叫格林戈特的妖精创立的。其主要办事处位于英格兰伦敦对角巷的北侧。除了为巫师和女巫存储金钱和贵重物品外,人们还可以去那里用麻瓜货币兑换巫师货币。麻瓜兑换的货币后来由妖精返还到麻瓜世界中流通。根据鲁伯斯·海格的说法,除了霍格沃茨魔法学校,古灵阁是巫师世界中最安全的地方。\u003cbr\u003e\u0026nbsp;\u0026nbsp;上述文本摘自《哈利·波特百科全书》。但现在古灵阁巫师银行不再安全了。愚蠢的达德利,哈利·波特的表亲,刚刚抢劫了银行。当然,背后操纵一切的是卖钻头的弗农叔叔,因为他拥有世界上最先进的钻头。达德利开着一台隐形无声的钻机进入银行,偷走了哈利·波特的巫师货币和麻瓜货币。邓布利多无法容忍这一切。他下令在银行房间里放一些魔法灯光来探测达德利的钻机。银行可以被看作是一个N×M网格,由N×M个房间组成。每个房间都有一个坐标。左上角房间的坐标是(1,1),右下角房间是(N,M),左上角房间下方的房间是(2,1)...... 下面展示了一个3×4的银行网格:\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/de7cbf2fbbe60d84487a2c9ea9e49149?v\u003d1707112095\"\u003e\u003c/center\u003e \u003cbr\u003e 有些房间是坚不可摧的,而有些房间是脆弱的。达德利的机器只能通过脆弱的房间。因此,必须在所有脆弱的房间里放灯光。银行中最多有十五个脆弱的房间。你最多可以在一个房间里放一个灯光。灯光可以穿透墙壁。如果你在房间(x,y)里放了灯光,它会照亮三个房间:房间(x,y),房间(x-1,y)和房间(x,y+1)。邓布利多只有一个特殊的灯光,它的照明方向可以调整为0度、90度、180度或270度。例如,如果特殊灯光放在房间(x,y)里,且其照明方向调整为90度,它将照亮房间(x,y),房间(x,y+1)和房间(x+1,y)。现在请帮助邓布利多找出至少需要使用多少灯光才能照亮所有脆弱的房间。\u003cbr\u003e 请注意,你不能照亮任何坚不可摧的房间,因为那里的妖精讨厌光线。 \u003cbr\u003e\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":" 有多个测试用例。\u003cbr\u003e 在每个测试用例中:\u003cbr\u003e 第一行是两个整数N和M,表示银行是一个N×M的网格(0\u0026lt;N,M \u0026lt;\u003d 200)。\u003cbr\u003e 然后是一个N×M的矩阵。每个元素是一个代表一个房间的字母。\u0027#\u0027表示坚不可摧的房间,\u0027.\u0027表示脆弱的房间。\u003cbr\u003e 输入以N \u003d 0和M \u003d 0结束。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":" 对于每个测试用例,打印邓布利多需要放置的最少灯光数量。\u003cbr\u003e 如果没有脆弱的房间,打印0。\u003cbr\u003e 如果邓布利多无法照亮所有脆弱的房间,打印-1。"}},{"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 2\r\n##\r\n##\r\n2 3\r\n#..\r\n..#\r\n3 3\r\n###\r\n#.#\r\n###\r\n0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n2\r\n-1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}