Задача: 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 int better(int x, int y) {
        return x < 0 || (y >= 0 && y < x) ? y : x;
    }

    private int dfs(int[][] mat, List<Integer> operations) {
        if (operations.size() == mat[0].length) {
            int[] changed = new int[mat[0].length];
            int[] lastState = operations.stream().mapToInt(i -> i).toArray();
            int maybe = 0;
            for (int[] row : mat) {
                int[] state = changed.clone();
                for (int j = 0; j < row.length; ++j) {
                    state[j] ^= row[j];
                    if (lastState[j] == 1) {
                        state[j] ^= 1;
                        if (j > 0) {
                            state[j - 1] ^= 1;
                        }
                        if (j + 1 < row.length) {
                            state[j + 1] ^= 1;
                        }
                        ++maybe;
                    }
                }
                changed = lastState;
                lastState = state;
            }
            for (int x : lastState) {
                if (x != 0) {
                    return -1;
                }
            }
            return maybe;
        }
        operations.add(0);
        int maybe1 = dfs(mat, operations);
        operations.set(operations.size() - 1, 1);
        int maybe2 = dfs(mat, operations);
        operations.remove(operations.size() - 1);
        return better(maybe1, maybe2);
    }

    public int minFlips(int[][] mat) {
        List<Integer> operations = new ArrayList<>();
        return dfs(mat, operations);
    }
}

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