Существует прямоугольная сетка монет, где решка представлена значением 1, а решка представлена значением 0. Вы представляете это с помощью таблицы двумерного целочисленного массива (от 1 до 10 строк/столбцов включительно).
На каждом ходу вы выбираете любую отдельную ячейку (R, C) в сетке (R-я строка, C-й столбец) и подбрасываете монеты во всех ячейках (r, c), где r находится в диапазоне от 0 до R включительно. , а c находится в диапазоне от 0 до C включительно. Подбрасывание монеты означает инвертирование значения ячейки от нуля до единицы или от единицы до нуля.
Возвращает минимальное количество ходов, необходимое для превращения всех ячеек сетки в решки. Это всегда будет возможно.
Примеры:
1111
1111
returns: 1
01
01
returns: 2
010101011010000101010101
returns: 20
000
000
001
011
returns: 6
Вот что я пробовал: поскольку порядок подбрасывания не имеет значения, а сделать ход монеты дважды — все равно, что вообще не делать ход, мы можем просто найти все различные комбинации подбрасывания монет и минимизировать размер положительного результата. комбинации(хорошие значения те, которые дают все решки).
Это можно сделать, составив набор, состоящий из всех монет, каждая из которых представлена индексом (т. Е. Если бы всего было 20 монет, этот набор содержал бы 20 элементов, присваивая им индекс от 1 до 20). Затем сделайте все возможные подмножества и посмотрите, какие из них дают ответ (т. е. дает ли нам ход монеты в подмножестве все решки). Наконец, минимизируйте размер хороших комбинаций.
Я не знаю, смог ли я выразить себя слишком ясно... Я опубликую код, если хотите. В любом случае, этот метод слишком трудоемкий и расточительный и невозможен для количества монет> 20 (в моем коде). Как это сделать?