← 返回题目列表

Codeforces · 1194/B

B. 又一个交叉问题

中文机器翻译题面 查看原题

给您一张由 $$$n$$$ 行和 $$$m$$$ 列组成的图片。行从上到下编号为 $$$1$$$ 到 $$$n$$$,列从左到右编号为 $$$1$$$ 到 $$$m$$$。每个单元都被漆成黑色或白色。

你觉得这张图不够有趣。如果一幅画中至少有一个十字架,您就认为它很有趣。十字由一对数字 $$$x$$$ 和 $$$y$$$ 表示,其中 $$$1 \le x \le n$$$ 和 $$$1 \le y \le m$$$,这样 $$$x$$$ 行中的所有单元格和 $$$y$$$ 列中的所有单元格都涂成黑色。

例如,这些图片中的每张都包含十字:

第四张图片包含 4 个十字架:位于 $$$(1, 3)$$$、$$$(1, 5)$$$、$$$(3, 3)$$$ 和 $$$(3, 5)$$$。

以下图像不包含十字:

你有一把画笔和一罐黑色颜料,所以你可以让这幅画变得有趣。每分钟您都可以选择一个白色单元格并将其涂成黑色。

要使生成的图片包含至少一个十字,您至少需要花费多少分钟?

您还需要回答多个独立的查询。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 5 \cdot 10^4$$$) — 查询数。

每个查询的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 5 \cdot 10^4$$$, $$$n \cdot m \le 4 \cdot 10^5$$$) — 图片中的行数和列数。

接下来的 $$$n$$$ 行包含 $$$m$$$ 个字符 — '.'如果单元格漆成白色,则为“*”;如果单元格漆成黑色,则为“*”。

保证 $$$\sum n \le 5 \cdot 10^4$$$ 和 $$$\sum n \cdot m \le 4 \cdot 10^5$$$。

输出

打印 $$$q$$$ 行,第 $$$i$$$ 行应包含一个整数 - 第 $$$i$$$ 查询的答案,这是您必须花费的最少分钟数,以便生成的图片至少包含一个十字。

示例

输入 #1

9
5 5
..*..
..*..
*****
..*..
..*..
3 4
****
.*..
.*..
4 3
***
*..
*..
*..
5 5
*****
*.*.*
*****
..*.*
..***
1 4
****
5 5
.....
..*..
.***.
..*..
.....
5 3
...
.*.
.*.
***
.*.
3 3
.*.
*.*
.*.
4 4
*.**
....
*.**
*.**

输出 #1

0
0
0
0
0
4
1
1
2

注意

该示例包含上面的所有图片,顺序相同。

前 5 张图片已经包含十字,因此您无需绘制任何内容。

您可以在第$$$6$$$图片上绘制$$$(1, 3)$$$、$$$(3, 1)$$$、$$$(5, 3)$$$和$$$(3, 5)$$$,以在$$$(3, 3)$$$中获得十字。这将花费您 $$$4$$$ 分钟。

您可以在第$$$7$$$张图片上绘制$$$(1, 2)$$$,以在$$$(4, 2)$$$中获得十字。

您可以在第$$$8$$$张图片上绘制$$$(2, 2)$$$,以在$$$(2, 2)$$$中获得十字。例如,您可以绘制 $$$(1, 3)$$$、$$$(3, 1)$$$ 和 $$$(3, 3)$$$ 以获得 $$$(3, 3)$$$ 中的十字,但这将花费您 $$$3$$$ 分钟,而不是 $$$1$$$。

在第$$$9$$$张图片上,您可以在最短的时间内获得 9 个可能的交叉。其中之一是$$$(1, 1)$$$:绘制$$$(1, 2)$$$ 和$$$(2, 1)$$$。