Задача: 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
Сложность: hard

Дана бинарная матрица mat размером m x n. За один шаг вы можете выбрать одну ячейку и перевернуть её и всех её четырех соседей, если они существуют (Перевернуть означает изменить 1 на 0 и 0 на 1). Пара ячеек называется соседями, если они имеют общую границу.

Верните минимальное количество шагов, необходимых для преобразования матрицы mat в нулевую матрицу или -1, если это невозможно.

Бинарная матрица - это матрица, в которой все ячейки равны 0 или 1.
Нулевая матрица - это матрица, в которой все ячейки равны 0.

Пример:

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.

👨‍💻 Алгоритм:

1⃣Переберите все возможные варианты решений для первой строки матрицы. Каждое решение представляется массивом, где каждый элемент равен 0 или 1, указывая, перевернут ли соответствующий элемент в первой строке. Инициализируйте два бинарных массива для каждой строки: lastState[], содержащий значения предыдущей строки, и changed[], представляющий, были ли значения в текущей строке перевернуты при работе с предыдущей строкой.

2⃣Для каждой строки в матрице используйте следующий шаг для вычисления состояния, инициализированного как changed:
Для каждой позиции j в диапазоне [0, n - 1] текущей строки измените значение state[j] соответственно, если lastState[j] равно 1. Переверните state[j], state[j - 1] и state[j + 1], если они существуют. Увеличьте счетчик переворотов на 1.
Значения, которые будут перевернуты в следующей строке, точно равны lastState, а решение для следующей строки точно равно массиву state. Поэтому установите changed = lastState и lastState = state, затем переходите к следующей строке.

3⃣После обработки всех строк проверьте, содержит ли lastState все нули, чтобы определить, является ли это допустимым решением. Верните минимальное количество переворотов для всех допустимых решений.

😎 Решение:

class Solution {
    private function better($x, $y) {
        return $x < 0 || ($y >= 0 && $y < $x) ? $y : $x;
    }

    private function dfs($mat, &$operations) {
        if (count($operations) == count($mat[0])) {
            $changed = array_fill(0, count($mat[0]), 0);
            $lastState = $operations;
            $maybe = 0;
            foreach ($mat as $row) {
                $state = $changed;
                foreach ($row as $j => $cell) {
                    $state[$j] ^= $cell;
                    if ($lastState[$j]) {
                        $state[$j] ^= 1;
                        if ($j > 0) {
                            $state[$j - 1] ^= 1;
                        }
                        if ($j + 1 < count($row)) {
                            $state[$j + 1] ^= 1;
                        }
                        $maybe++;
                    }
                }
                $changed = $lastState;
                $lastState = $state;
            }
            foreach ($lastState as $x) {
                if ($x) {
                    return -1;
                }
            }
            return $maybe;
        }
        $operations[] = 0;
        $maybe1 = $this->dfs($mat, $operations);
        $operations[count($operations) - 1] = 1;
        $maybe2 = $this->dfs($mat, $operations);
        array_pop($operations);
        return $this->better($maybe1, $maybe2);
    }

    public function minFlips($mat) {
        $operations = [];
        return $this->dfs($mat, $operations);
    }
}

Ставь 👍 и забирай 📚 Базу знаний