{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"全球空中研究中心被分配了在瑞典建造第五代移动电话网络的任务。他们得到这项工作最引人注目的原因是他们发现了一种新的、高噪声抗性的天线。它被称为4DAir,有四种类型。每种类型只能在与(略微倾斜的)纬度和经度网格对齐的方向上发送和接收信号,这是因为地球的相互作用电磁场。这四种类型对应于分别在北、西、南和东方向上运行的天线。下面是一个感兴趣的地点的示例图片,由十二个小圆环表示,以及由椭圆形覆盖它们的九个4DAir天线。\r\u003cbr\u003e\u003cimg src\u003d\"CDN_BASE_URL/6029179dab991d91c2e625a9ba1b27d4?v\u003d1711664473\"\u003e\r\u003cbr\u003e显然,希望使用尽可能少的天线,但仍然为每个感兴趣的地点提供覆盖。我们将问题建模如下:设A是描述瑞典地表的矩阵,其中A的一个条目要么是一个感兴趣的点,必须至少被一个天线覆盖,要么是空白空间。天线只能放置在A的一个条目上。当一个天线放置在第r行和第c列时,这个条目被认为是被覆盖的,但也被选择为这个特定天线的类型的(c+1,r),(c,r+1),(c-1,r)或(c,r-1)中的一个相邻条目被覆盖。存在这样一个放置在A中的所有感兴趣的点都被覆盖的最小天线数是多少?\r\u003cbr\u003e\r\u003cbr\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入的第一行是一个正整数n,表示接下来的情景数。每个情景以包含两个正整数h和w的行开始,其中1 \u003c\u003d h \u003c\u003d 40,0 \u003c\u003d w \u003c\u003d 10。然后是一个矩阵,描述了瑞典的感兴趣的点,格式为h行,每行包含来自集合[\u0027*\u0027,\u0027o\u0027]的w个字符。\u0027*\u0027字符表示一个感兴趣的点,而\u0027o\u0027字符表示空白空间。\r\u003cbr\u003e\r\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个情景,在其自己的一行上输出覆盖情景矩阵中所有\u0027*\u0027条目所需的最小天线数。"}},{"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\r\n7 9\r\nooo**oooo\r\n**oo*ooo*\r\no*oo**o**\r\nooooooooo\r\n*******oo\r\no*o*oo*oo\r\n*******oo\r\n10 1\r\n*\r\n*\r\n*\r\no\r\n*\r\n*\r\n*\r\n*\r\n*\r\n*\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e17\r\n5\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}