问题分析

我们有一排 $n$ 个格子，每个格子要么是空（.），要么是阻塞（#）。
目标：让所有空格子最终都有水。
允许两种操作：

1. 在一个空单元格中放置水（操作 $1$）；
2. 从一个已有水的单元格取出水，并放入任意另一个空单元格（操作 $2$）。

此外，有一个自动填充规则：若某个空单元格 $i$（$2\le i\le n-1$）的左右邻居 $i-1$ 和 $i+1$ 都已经有水，则 $i$ 会自动被水填满。

求最少需要执行多少次操作 $1$。操作 $2$ 次数不限。

关键观察

• 如果存在连续三个空单元格 $i-1, i, i+1$，那么我们可以先在 $i-1$ 和 $i+1$ 中放置水（两次操作 $1$），此时 $i$ 自动填满。
• 然后，我们可以从 $i$ 中取出水，放入任意其他空单元格（操作 $2$）。由于 $i-1$ 和 $i+1$ 仍然有水，$i$ 会再次自动填满。
• 这意味着：只要有三连空，我们就能用 $2$ 次操作 $1$ 来“复制”出无限多的水，从而填满所有空单元格。
• 反之，如果没有三连空，那么自动填充规则永远不会被触发（因为任何自动填充都要求三个连续格子均为空，且两侧已经人为放水）。此时必须逐个在所有空单元格中执行操作 $1$，即操作 $1$ 次数等于空单元格总数。

算法步骤

1. 读入测试用例数 $t$。
2. 对每个测试用例：
   • 读入 $n$ 和字符串 $s$。
   • 初始化 empty_cnt = 0，has_three = false。
   • 遍历 $i$ 从 $0$ 到 $n-1$：
     • 若 $s[i] == '.'$，则 empty_cnt++；
     • 同时检查 $i \ge 2$ 且 $s[i-2] == '.'$ 且 $s[i-1] == '.'$，若是则 has_three = true。
   • 若 has_three == true，输出 $2$；否则输出 empty_cnt。

时间复杂度 $O(n)$，空间复杂度 $O(1)$（不计输入存储）。

正确性证明

情况一：存在三个连续空单元格
设三个连续空位置为 $p, p+1, p+2$。

1. 在 $p$ 和 $p+2$ 中执行操作 $1$（两次）。此时 $p+1$ 因左右邻居有水而自动填满。
2. 现在 $p, p+1, p+2$ 都有水。
3. 对于任意其他空单元格 $x$：
   • 使用操作 $2$ 从 $p+1$ 取出水，放入 $x$。
   • 由于 $p$ 和 $p+2$ 仍然有水，$p+1$ 会再次自动填满（因为它的左右邻居仍然有水）。
   • 重复此过程，即可用无限次操作 $2$ 将水扩散到所有空单元格。
     因此只需要 $2$ 次操作 $1$。并且显然不可能少于 $2$ 次（因为至少需要两个水源才能触发自动填充）。

情况二：不存在三个连续空单元格
自动填充规则永远不会生效（因为需要三个连续空位，且中间的空位必须左右都有水；但既然没有三个连续空位，任何水都无法通过自动规则传播到新的空单元格）。
因此，每个空单元格都必须通过操作 $1$ 单独放置水。所以答案就是空单元格的数量。

边界情况：

• $n < 3$：不可能有三个连续空位，因此答案直接是空单元格数。
• 没有空单元格：empty_cnt = 0，输出 $0$。

示例验证

以题目给出的测试用例为例：

1. 3 ...
   存在三个连续空 → 输出 $2$。
2. 7 ##....#
   子串 "..." 从下标 $2$ 到 $4$ 存在 → 输出 $2$。
3. 7 ..#.#..
   空位有 $5$ 个，但没有三个连续空 → 输出 $5$。
4. 4 ####
   空位 $0$ → 输出 $0$。
5. 10 #...#..#.#
   空位分布：下标 $1,2,3,5,6,8$（共 $6$ 个），但存在 "..." 吗？检查：
   • 下标 $1,2,3$ 是 ... → 存在三连空 → 输出 $2$。

全部匹配输出。

复杂度分析

• 时间：每个测试用例扫描一次字符串，$O(\sum n) \le 100 \times 100 = 10^4$，轻松通过。
• 空间：仅使用常数个变量，$O(1)$。

总结

• 核心结论：如果存在三个连续的空单元格，答案为 $2$；否则答案为空单元格总数。
• 原因：三连空可以借助自动填充和水的移动（操作 $2$）实现无限复制水，从而仅需最初的两个水源。
• 实现简单，只需扫描判断是否有 "..." 子串，并统计 '.' 个数即可。