{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"全球航空研究中心被分配在瑞典建造第五代移动电话网的任务。他们得到这份工作最引人注目的原因是他们发现了一种新的高抗噪天线。它被称为4DAir,有四种类型。由于地球相互作用的电磁场,每种类型只能在与(略微倾斜的)纬度和纵向网格对齐的方向上发送和接收信号。这四种类型分别对应于在北、西、南和东方向工作的天线。下面是一幅风景名胜的示例图片,由十二个小环和九个由椭圆覆盖的4DAir天线描绘。\n\u003cbr\u003e\u003cimg src\u003d\"CDN_BASE_URL/6029179dab991d91c2e625a9ba1b27d4?v\u003d1628505159\"\u003e 显然,希望使用尽可能少的天线,但仍然为每个感兴趣的地方提供覆盖。我们将问题建模如下:假设A是描述瑞典表面的矩形矩阵,其中A的入口或是一个关注点,必须由至少一个天线或空白空间覆盖。天线只能放置在A中的入口。当天线放置在第r行和第c列时,该条目被视为已覆盖,但相邻条目之一(c+1,r)、(c,r+1)、(c-1,r)或(c,r-1)也被覆盖,具体取决于为该特定天线选择的类型。天线的最小数量是多少?天线的位置应确保覆盖所有关注点?"}},{"title":"Input","value":{"format":"HTML","content":"输入的第一行是一个正整数n,指定接下来的场景数。每个场景都从一行开始,该行包含两个正整数h和w,其中1 \u003c\u003d h \u003c\u003d 40和0 \u003c w \u003c\u003d 10。此后,将呈现一个矩阵,以h行的形式描述瑞典的关注点,每个矩阵包含集合[\u0027*\u0027,o\u0027]中的w个字符。“*”字符表示兴趣点,而“o”字符表示开放空间。"}},{"title":"Output","value":{"format":"HTML","content":"对于每个场景,输出覆盖场景矩阵中所有“*”项所需的最小天线数,每行一个。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e2\n7 9\nooo**oooo\n**oo*ooo*\no*oo**o**\nooooooooo\n*******oo\no*o*oo*oo\n*******oo\n10 1\n*\n*\n*\no\n*\n*\n*\n*\n*\n*\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e17\n5\u003c/pre\u003e"}}]}