У Филиппа есть ряд клеток, некоторые из которых заблокированы, а остальные — пусты. Он хочет, чтобы во всех пустых клетках оказалась вода. Для этого он может применять 2 типа операций:
- \(1\) — поместить воду в пустую клетку.
- \(2\) — переместить воду из клетки с водой в любую другую пустую клетку. Обратите внимание, что при перемещении воды из одной клетки в другую Филипп удаляет воду из начальной клетки.
Если клетка \(i\) (\(2 \le i \le n-1\)) пустая, а клетки \(i-1\) и \(i+1\) содержат воду, то она заполняется водой.
Найдите минимальное количество раз, которое ему нужно выполнить операцию \(1\) типа, чтобы заполнить все пустые клетки водой.
Заметим, что минимизировать использование операций \(2\) типа не нужно. Также заметим, что заблокированные клетки не содержат воду, и Филипп не может поместить в них воду.
Выходные данные
Для каждого набора входных данных выведите единственное число — минимальное количество операций \(1\) типа, необходимое для заполнения всех пустых клеток водой.
Примечание
Набор входных данных 1
В первом наборе входных данных Филипп может поместить воду в клетки \(1\) и \(3\). Поскольку клетка \(2\) находится между \(2\) клетками с водой, она тоже заполняется водой.
Набор входных данных 2
Во втором наборе он может поместить источники воды в клетки \(3\) и \(5\). В результате клетка \(4\) заполнится водой. Затем он удалит воду из клетки \(5\) и поместит ее в клетку \(6\). Поскольку соседи клетки \(5\) — клетки \(4\) и \(6\) — имеют воду, клетка \(5\) также заполняется водой. Иллюстрация этого процесса приведена ниже.
Операции во втором наборе входных данных. Белые клетки — пустые, серые — заблокированные, синие — вода. Набор входных данных 3
В третьем наборе входных данных он может поместить воду во все пустые клетки. Для этого требуется \(5\) операций \(1\) типа.
Набор входных данных 4
В четвертом наборе пустых клеток нет. Следовательно, ни одной операции применять не нужно.
Набор входных данных 5
В пятом наборе входных данных существует последовательность операций, которая требует только \(2\) операции типа \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
...
7
##....#
7
..#.#..
4
####
10
#...#..#.#
|
2
2
5
0
2
|