Задача Камеры Наблюдения (CAMERAS)

Менеджер по безопасности нарисовал план этажа на клетчатой бумаге размерами  клеток. Клетка закрашена, если в этом месте находится стена. Клетка не закрашена (свободна), если в этом месте нет стены. Менеджеру нужно расставить камеры слежения на этаже.

Каждую камеру можно разместить одним из следующих способов:

1.        В свободную клетку. Эта клетка будет под наблюдением.

2.        Между двумя свободными клетками, имеющими общую сторону. В этом случае обе клетки окажутся под наблюдением камеры.

3.        Между четырьмя свободными клетками, имеющими общую точку. Все четыре клетки будут под наблюдением.

Каждая клетка должна находиться под наблюдением ровно одной камеры. Менеджер твердо намерен нарисовать все возможные варианты расположения камер прежде чем выбрать из них наилучший. Каждый день менеджер рисует 75 вариантов расположения. Разумеется, в последний день работы он рисует все оставшиеся варианты, которых может оказаться и меньше чем 75. Определите, сколько вариантов работящий менеджер нарисует в последний день работы.

Формат ввода/вывода:

Напишите программу CAMERAS, которая читает из файла CAMERAS.DAT план этажа и выводит в файл CAMERAS.SOL число вариантов расположения камер слежения, которые менеджер нарисует в последний день работы.

В первой строке файла CAMERAS.DAT находятся числа  разделенные пробелом – размеры плана. В последующих  строках находятся по  чисел разделенные пробелом – план этажа. Число  соответствует закрашенной клетке,  – свободной клетке.

Ограничения: , .

Пример: (см. рисунок, на котором изображены все восемь вариантов расположения для этого примера, причем черным прямоугольником обведены клетки, находящиеся под наблюдением одной камеры)