Задача №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