← 返回题目列表

Codeforces · 1997/B

B. 制作三个区域

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

有一个网格,由 $$$2$$$ 行和 $$$n$$$ 列组成。网格的每个单元格要么空闲,要么被阻塞。

如果至少满足以下条件之一,则可以从空闲单元格 $$$x$$$ 访问空闲单元格 $$$y$$$:

- $$$x$$$ 和 $$$y$$$ 共享一边;
- 存在一个空闲单元$$$z$$$,使得$$$z$$$可以从$$$x$$$到达并且$$$y$$$可以从$$$z$$$到达。

连接区域是网格的一组空闲单元,其中的所有单元都可以相互访问,但向该组添加任何其他空闲单元会违反此规则。

例如,考虑以下布局,其中白色单元格空闲,深灰色单元格被阻挡:

其中有$$$3$$$区域,分别用红、绿、蓝色表示:

给定网格最多包含 $$$1$$$ 连接区域。您的任务是计算满足以下约束的空闲单元的数量:

- 如果此单元格被阻挡,则连接区域的数量恰好变为$$$3$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 列数。

接下来两行的第 $$$i$$$ 包含网格第 $$$i$$$ 行的描述 — 字符串 $$$s_i$$$,由 $$$n$$$ 字符组成。每个字符都是 . (表示空闲单元)或 x(表示阻塞单元)。

输入的附加约束:

- 给定网格最多包含 $$$1$$$ 连接区域;
- 所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 单元格数量,如果该单元格被阻塞,则连接区域的数量将变为 $$$3$$$。

示例

输入 #1

4
8
.......x
.x.xx...
2
..
..
3
xxx
xxx
9
..x.x.x.x
x.......x

输出 #1

1
0
0
2

注意

在第一个测试用例中,如果单元格 $$$(1, 3)$$$ 被阻塞,则连接区域的数量变为 $$$3$$$ (如语句中的图片所示)。