CF1997B Make Three Regions

题目描述

有一个由 $2$ 行 $n$ 列组成的网格。网格中的每个格子要么是空的，要么是被阻塞的。

如果至少满足以下条件之一，则空格 $y$ 可以从空格 $x$ 到达：

• $x$ 和 $y$ 有公共边；
• 存在一个空格 $z$，使得 $z$ 可以从 $x$ 到达，且 $y$ 可以从 $z$ 到达。

一个连通区域是指网格中一组空格，这些格子两两可达，并且如果再加入任意一个其他空格，这个性质就不成立。

例如，考虑下图，白色格子为空，深灰色格子为阻塞：

其中有 $3$ 个连通区域，分别用红色、绿色和蓝色表示：

给定的网格最多只包含 $1$ 个连通区域。你的任务是计算有多少个空格满足以下条件：

• 如果将该格子阻塞，连通区域的数量恰好变为 $3$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示列数。

接下来两行，每行一个长度为 $n$ 的字符串 $s_i$，表示第 $i$ 行的网格。每个字符为 .（表示空格）或 x（表示阻塞格）。

输入的额外约束：

• 给定的网格最多只包含 $1$ 个连通区域；
• 所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示有多少个格子满足：如果将该格子阻塞，连通区域的数量恰好变为 $3$。

输入输出样例 #1

输入 #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$（如题目中的图片所示）。

由 ChatGPT 4.1 翻译