A16306 | $Cover in Water$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

Filip has a row of cells, some of which are blocked, and some are empty. He wants all empty cells to have water in them. He has two actions at his disposal: - $1$ — place water in an empty cell. - $2$ — remove water from a cell and place it in any other empty cell. If at some moment cell $i$ ( $2 \le i \le n-1$ ) is empty and both cells $i-1$ and $i+1$ contains water, then it becomes filled with water. Find the minimum number of times he needs to perform action $1$ in order to fill all empty cells with water. Note that you don't need to minimize the use of action $2$ . Note that blocked cells neither contain water nor can Filip place water in them.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 100$ ). The description of the test cases follows. The first line of each test case contains a single integer $n$ ( $1 \le n \le 100$ ) — the number of cells. The next line contains a string $s$ of length $n$ . The $i$ -th character of $s$ is '.' if the cell $i$ is empty and '\#' if cell $i$ is blocked.

For each test case, output a single number — the minimal amount of actions $1$ needed to fill all empty cells with water.

输入 #1

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

输出 #1

C++ 编辑器

输入

输出