Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
99. Максимальная расстановка
Максимальное паросочетаниеОлимпиадные задачи на русском языке
| 06/10/2006 | Личное первенство Южного Урала (F) |
| 20/12/2008 | Занятие 12 (B) |
| 09/03/2011 | Занятие 16 (F) |
| 02/04/2014 | Занятие 19 (C) |
| 15/07/2019 | Лето 2019 - 7 (D) |
| 04/03/2023 | Паросочетание (проводит BOGAT) (B) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (5)
Задано прямоугольное поле размером `N` строк на `M` столбцов, клетки которого окрашены в черный или белый цвет. Требуется расставить максимальное количество шахматных коней на белые клетки поля таким образом, чтобы ни один конь не бил другого. В клетку можно поставить не более одного коня.
Ввод
В первой строке входного файла содержится два целых числа `N` и `M\ (1\ ≤\ N,\ M\ ≤\ 50)`, разделенных пробелом. Далее следуют `N` строк, содержащих `M` символов каждая, задающих поле. В строке `i`-ой на `j`-ой позиции содержится символ '.', если клетка белая, либо '#', если клетка черная.
Вывод
Вывести единственную строку, содержащую максимальное количество коней, которое можно расставить на заданном поле.
Пример ввода 1
2 2 .. ..
Пример вывода 1
4
Пример ввода 2
4 5 #...# #.#.# #.... ..#..
Пример вывода 2
7
