Задача №114310. Парковка

Город Загреб решил построить новую парковку. Для этого было решено использовать прямоугольный участок земли, который можно представить в виде матрицы с \(N\) строками и \(M\) столбцами. Чтобы привлечь гостей и увеличить доходы, мэр решил разместить фонтаны на заранее определенных участках земли. Остальные же клетки будут преобразованы в парковочные места и дороги. Машины могут двигаться по парковке, перемещаясь в соседнее поле в одном из четырех направлений (север, юг, восток или запад). При этом парковочные места должны быть выбраны так, чтобы любая припаркованная машина могла выехать из парковки, то есть иметь возможность попасть в левую верхнюю клетку, не врезаясь в другие припаркованные машины.

Помогите мэру и определите максимально возможное количество парковочных мест для данного участка.

Входные данные

Первая строка содержит натуральные числа \(N\) и \(M\) \((1 \le N \le 6, 1 \le M \le 100)\) – количество строк и столбцов участка.

Следующие \(N\) строк содержат \(M\) символов, каждый из которых описывает состояние соответствующей клетки – знак «x» обозначает клетку, на которой будет построен фонтан, другие клетки помечены знаком «.» и будут преобразованы в парковку.

Выходные данные

На единственной строке выведите максимальное количество парковочных мест.

Система оценки

В этой задаче 6 подгрупп.

  • (10 баллов) Ограничения: \(N, M \le 4\)
  • (10 баллов) Ограничения: \(N = 2\)
  • (20 баллов) Ограничения: \(N = 3\)
  • (20 баллов) Ограничения: \(N = 4\)
  • (20 баллов) Ограничения: \(N = 5\)
  • (20 баллов) Ограничения: \(N = 6\)

Примечание

Поле в первой строке и первом столбце является входом на парковку и не предназначено для парковки.

Примеры
Входные данные
3 3
...
.x.
...
Выходные данные
2
Входные данные
3 3
...
..x
...
Выходные данные
4
Входные данные
3 6
.x..x.
..x.x.
......
Выходные данные
3
Входные данные
4 5
....x
....x
..x..
.x..x
Выходные данные
7
Сдать: для сдачи задач необходимо войти в систему