Codeforces Round 911 (Div. 2) |
---|
Закончено |
У Филиппа есть ряд клеток, некоторые из которых заблокированы, а остальные — пусты. Он хочет, чтобы во всех пустых клетках оказалась вода. Для этого он может применять 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$$$) — количество клеток.
Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$. $$$i$$$-й символ $$$s$$$ равен '.', если клетка $$$i$$$ пуста, и '#', если клетка $$$i$$$ заблокирована.
Для каждого набора входных данных выведите единственное число — минимальное количество операций $$$1$$$ типа, необходимое для заполнения всех пустых клеток водой.
53...7##....#7..#.#..4####10#...#..#.#
2 2 5 0 2
Набор входных данных 1
В первом наборе входных данных Филипп может поместить воду в клетки $$$1$$$ и $$$3$$$. Поскольку клетка $$$2$$$ находится между $$$2$$$ клетками с водой, она тоже заполняется водой.
Набор входных данных 2
Во втором наборе он может поместить источники воды в клетки $$$3$$$ и $$$5$$$. В результате клетка $$$4$$$ заполнится водой. Затем он удалит воду из клетки $$$5$$$ и поместит ее в клетку $$$6$$$. Поскольку соседи клетки $$$5$$$ — клетки $$$4$$$ и $$$6$$$ — имеют воду, клетка $$$5$$$ также заполняется водой. Иллюстрация этого процесса приведена ниже.
Набор входных данных 3
В третьем наборе входных данных он может поместить воду во все пустые клетки. Для этого требуется $$$5$$$ операций $$$1$$$ типа.
Набор входных данных 4
В четвертом наборе пустых клеток нет. Следовательно, ни одной операции применять не нужно.
Набор входных данных 5
В пятом наборе входных данных существует последовательность операций, которая требует только $$$2$$$ операции типа $$$1$$$.
Название |
---|