Мозаика из доминошек
Художник выкладывает мозаику из доминошек на тёмной части фотографии. Фотография разбита на клетки; доминошка закрывает ровно две соседние по стороне клетки, обе должны быть тёмными, и доминошки не перекрываются. Сколько доминошек поместится?
Два теста — настоящие фотографии автора сайта, те же, что в мозаике статьи: «Буря» и «Озеро Иссык», клетка — средняя яркость квадрата 3 × 3 пикселя.
Вход
В первой строке n и m (1 ≤ n, m ≤ 200) — число строк и столбцов. Дальше n строк по m символов: . — тёмная клетка, её можно закрыть, # — светлая, её закрывать нельзя.
Выход
Наибольшее число доминошек.
Примеры
Пример 1
3 4 ..#. .... #...
4
Пример 2
4 6 ..##.. .#..#. ..##.. ......
8
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Раскрасьте клетки, как шахматную доску. Какого цвета две клетки под одной доминошкой?
2Подсказка 2
Хватит ли посчитать клетки каждого цвета и взять меньшее? Проверьте на втором примере.
3Идея
Доминошка всегда закрывает одну чёрную и одну белую клетку. Значит, раскладка — это паросочетание в двудольном графе: слева чёрные тёмные клетки, справа белые, ребро — соседство по стороне. Наибольшее число доминошек — наибольшее паросочетание, его находит алгоритм Хопкрофта — Карпа.
4Разбор
Нумеруем тёмные клетки отдельно по цветам, для каждой чёрной составляем список соседних белых — не больше четырёх. Дальше Хопкрофт — Карп: обход в ширину от всех свободных чёрных клеток строит слои по длине чередующегося пути, затем поиск в глубину по слоям находит много кратчайших увеличивающих путей без общих клеток, и каждый переворачивается — доминошек становится на одну больше.
Подсчёт цветов даёт только верхнюю границу. Во втором примере тёмных клеток 18 — девять чёрных и девять белых, — а доминошек восемь. Слева четыре белые клетки граничат всего с тремя чёрными, справа наоборот: четыре чёрные — с тремя белыми. С каждой стороны одна клетка остаётся без пары, как ни раскладывай. Это теорема Холла; в статье такие области можно увидеть на фотографии, коснувшись красной клетки.
Длинный коридор в одну клетку шириной (седьмой тест) даёт увеличивающие пути в тысячи шагов: рекурсивный поиск в глубину на Python упрётся в предел глубины рекурсии, поэтому стек — свой, списком.
4+Решение
5Сложность
O(E √V), где V ≤ 40 000 клеток и E ≤ 4V соседств. Простой алгоритм Куна — O(V E) в худшем случае, на этих полях он тоже успевает, но медленнее.
6Типичные ошибки
- Подсчёт цветов. min(чёрных, белых) — ответ только для фигур без «узких мест»: второй, третий, четвёртый и пятый тесты.
- Жадная раскладка. Класть доминошку на первую свободную пару слева направо — легко запереть одиночные клетки.
- Рекурсия. Глубина пути доходит до половины клеток — седьмой тест.