Загрузка [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

printРабочее место участника

printЗадачи

99. Максимальная расстановка

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (5)

Задано прямоугольное поле размером N строк на M столбцов, клетки которого окрашены в черный или белый цвет. Требуется расставить максимальное количество шахматных коней на белые клетки поля таким образом, чтобы ни один конь не бил другого. В клетку можно поставить не более одного коня.
Ввод
В первой строке входного файла содержится два целых числа N и M (1  N, M  50), разделенных пробелом. Далее следуют N строк, содержащих M символов каждая, задающих поле. В строке i-ой на j-ой позиции содержится символ '.', если клетка белая, либо '#', если клетка черная.
Вывод
Вывести единственную строку, содержащую максимальное количество коней, которое можно расставить на заданном поле.

Пример ввода 1

2 2
..
..

Пример вывода 1

4

Пример ввода 2

4 5
#...#
#.#.#
#....
..#..

Пример вывода 2

7
loading