Погасить все лампочки
Головоломка: поле из r × c лампочек, часть горит. Нажатие на лампочку переключает её саму и её соседей по сторонам — до четырёх штук: горевшие гаснут, погасшие загораются. Нужно погасить все лампочки. За какое наименьшее число нажатий это можно сделать?
В первом примере — классическое поле 5 × 5, на котором горит всё.
Вход
В первой строке r и c (1 ≤ r, c ≤ 20). Дальше r строк по c символов: 1 — лампочка горит, 0 — нет.
Выход
Наименьшее число нажатий, после которых не горит ни одна лампочка, или -1, если так сделать нельзя.
Примеры
Пример 1
5 5 11111 11111 11111 11111 11111
15
Пример 2
2 3 100 110
1
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Важен ли порядок нажатий? Что будет, если нажать одну лампочку дважды?
2Подсказка 2
Каждая лампочка в итоге переключается столько раз, сколько нажали её саму и её соседей. Погаснет она, если это число той же чётности, что её начальное состояние. Запишите это уравнениями, где сложение — исключающее «или».
3Подсказка 3
Решений может быть много. Чем отличаются два решения друг от друга?
4Идея
Нажатия переставимы, а двойное нажатие ничего не меняет, поэтому решение — это множество нажатых лампочек, по одному неизвестному xk ∈ {0, 1} на клетку. Для каждой лампочки: сумма x по ней и её соседям по модулю 2 равна её начальному состоянию. Это система из rc линейных уравнений над полем из двух элементов, где сложение — XOR, а умножение — AND, и метод Гаусса работает в нём дословно: вычесть строку — значит сделать XOR, а делить на ведущий элемент не нужно, он всегда равен 1.
Если в конце остаётся строка «0 = 1», погасить всё нельзя. Иначе решения образуют сдвиг ядра: частное решение плюс любая сумма базисных векторов ядра — по одному на каждый столбец без ведущего элемента. Число нажатий — число единиц в решении, и наименьшее ищется перебором всех 2k комбинаций ядра. Для полей до 20 × 20 размерность ядра не больше 16 (такая у поля 19 × 19), так что комбинаций не больше 65 536.
5Разбор
Храним строку уравнения как битовую маску из rc + 1 бит: какие нажатия влияют на лампочку и, в последнем бите, горит ли она. Метод Гаусса — Жордана: для каждого столбца находим строку с единицей, ставим её на место и XOR-ом зануляем этот столбец во всех остальных строках, выше и ниже. Частное решение — свободные переменные равны нулю, переменная каждого ведущего столбца равна последнему биту своей строки. Базисный вектор ядра для свободного столбца f: единица в f и в тех ведущих столбцах, в строках которых стоит единица в столбце f.
Перебор: проходим комбинации в порядке кода Грея — соседние отличаются одним вектором, поэтому каждый шаг — один XOR и подсчёт единиц. На поле 5 × 5, где горит всё, ядро двумерно, четыре решения, и самое короткое — 15 нажатий.
Почему не «гонять огни»: нажимать под каждой горящей лампочкой, спускаясь по строкам. Так гаснет всё, кроме последней строки, и только при удачных нажатиях в первой строке — последняя тоже. На поле 5 × 5 с пустой первой строкой нажатий последняя строка остаётся гореть, хотя решение есть.
5+Решение
6Сложность
Исключение — O((rc)³/64) операций над 64-битными словами: при 400 клетках это меньше миллиона. Перебор ядра — O(2k·rc/64), где k ≤ 16.
7Типичные ошибки
- Гонять огни сверху вниз. Находит решение только при удачном выборе первой строки и не ищет самое короткое — первый тест.
- Любое решение вместо наименьшего. Частное решение из метода Гаусса почти никогда не самое короткое: на поле 19 × 19 у одной и той же картины 65 536 решений.
- Дроби и деление. Над обычными числами система другая: нажатия дают сумму, а не чётность. Всё считается по модулю 2.