← 返回题目列表

Codeforces · 1900/A

A. 盖在水中

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

Filip有一排单元格,其中一些被封锁,一些是空的。他希望所有空的细胞里都有水。他有两个行动可供选择:

- $$$1$$$ — 将水放入空单元格中。
- $$$2$$$ — 从单元格中除去水并将其放入任何其他空单元格中。

如果在某个时刻单元格 $$$i$$$ ($$$2 \le i \le n-1$$$) 为空,并且单元格 $$$i-1$$$ 和 $$$i+1$$$ 都含有水,那么它就会充满水。

找出他需要执行动作 $$$1$$$ 才能将所有空单元格注满水的最少次数。

请注意,您不需要最小化操作 $$$2$$$ 的使用。请注意,阻塞的细胞既不含水,菲利普也不能将水放入其中。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 单元格数量。

下一行包含长度为 $$$n$$$ 的字符串 $$$s$$$。 $$$s$$$ 的第 $$$i$$$ 个字符是“.”如果单元格 $$$i$$$ 为空,则为“#”;如果单元格 $$$i$$$ 被阻止,则为“#”。

输出

对于每个测试用例,输出一个数字 - 将所有空单元格注满水所需的最小操作量 $$$1$$$。

示例

输入 #1

5
3
...
7
##....#
7
..#.#..
4
####
10
#...#..#.#

输出 #1

2
2
5
0
2

注意

测试用例1

在第一个测试用例中,Filip 可以将水放入单元格 $$$1$$$ 和 $$$3$$$ 中。由于单元格 $$$2$$$ 位于 $$$2$$$ 单元格之间且有水,因此它也会充满水。

测试用例2

在第二种情况下,他可以将水源放入单元格$$$3$$$和$$$5$$$中。这会导致单元格 $$$4$$$ 充满水。然后他将从 $$$5$$$ 单元中除去水并将其放入 $$$6$$$ 单元中。由于单元格 $$$5$$$ 的邻居单元格 $$$4$$$ 和单元格 $$$6$$$ 中有水,因此单元格 $$$5$$$ 也充满了水。您可以在下面看到此案例的插图。

第二个测试用例中的操作。白色的细胞是空的,灰色的细胞被堵塞,蓝色的细胞是水。

测试用例3

在第三种情况下,他可以将水放入所有空单元格中。这需要 $$$5$$$ 类型的操作 $$$1$$$。

测试用例4

在第四种情况下,没有空单元格。因此,他不必在其中放任何水。

测试用例5

在第五个测试用例中,存在仅需要 $$$2$$$ 类型 $$$1$$$ 操作的操作序列。