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, 3)$ 阻塞，连通区域的数量会变为 $3$（如题目中的图片所示）。
由 ChatGPT 4.1 翻译