Конвертировать бинарную матрицу в 0-матрицу за миниальное число шагов

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

Нужно вернуть минимальное клочисество шагов, чтобы конвертировать mat в 0-матрицу (состоит только из 0) или -1, если это невозможно.

Пример 1:

Дано: mat = [[0,0],[0,1]]
Результат: 3
Пояснение: Мы инвертируем ячейку [1,0], затем [0, 1], затем [1, 1]. Результаты этой инверсии показаны на рисунке выше.

Пример 2:

Дано: mat = [[0]]
Результат: 0
Пояснение: Исходная матрица уже 0-матрица, никаких инверсий не требуется.

Пример 3:

Дано: mat = [[1,1,1],[1,0,1],[0,0,0]]
Результат: 6

Пример 4:

Дано: mat = [[1,0,0],[1,0,0]]
Результат: -1
Пояснение: Не существует такой последовательности шагов инверсии, чтобы получилась 0-матрица.

Ограничения:

• m == mat.length
• n == mat[0].length
• 1 <= m <= 3
• 1 <= n <= 3
• mat[i][j] состоит из 0 и 1.

Идея решения

Поскольку у нас бинарная матрица, то мы можем представитьеё в виде двоичного числа, соединив все строки в одну строку.
Если мы рассмотрим пример 1, то исходная матрица = это число 0001, затем мы конвертировали её в 1010, затем в 0111, и наконец получили 0000.

Заметим, что матриц размера m x n может быть 2^(m*n) штук. Мы можем использовать массив такого размера, где каждый его элемент под номером Х - это количество шагов, чтобы перейти из исходной матрицы в матрицу с содержимым X_в_двоичной_форме.

Мы берем исходную матрицу, и стартуя с каждого её элемента поиском в ширину ищем комбинацию инверсий, которые в итоге дадут 0-матрицу.

Компилируемое решение

public int minFlips(int[][] mat) {
    int numelems = mat.length * mat[0].length;   
    //все возможные матрицы размера m*n
    int[] path = new int[(int)Math.pow(2, numelems) + 1];
    int flips = getFlips(mat, path, mat.length, mat[0].length);
    return flips;
}

 private int getFlips(int[][] mat, int[] path, int height, int width) {
     // а вдруг нам на вход поступила 0-матрица?
    int firstBit = mat2bit(mat);
    if ((firstBit^0) == 0) return mat[0][0];
     
    // Если мы не вышли, то у нас не 0-матрица, считаем
    // создаем очередь для поиска в ширину
    Queue<Integer> q = new LinkedList<Integer>();
    // помещаем в очередь исходную матрицу в двоичном представлении
    q.add(firstBit);
    
    while (!q.isEmpty()) {
        // пока очередь не пуста, берем доступный элемент (двоичное число)
        int curBit = q.remove();
        // конвертируем двоичное число в бинарную матрицу
        int[][]m = bit2mat(curBit, height, width);
        
        // рассматриваем каждый элемент матрицы
        for (int i = 0; i < m.length; i++) {
            for (int j = 0; j < m[i].length; j++) {
                // инвертируем ячейку (i,j) и её соседей
                m = flip(m, i, j); // matrix snippet
                // смотрим двоичное представление полученной матрицы
                int mbit = mat2bit(m);
               
        // если у нас опять получилось число соответствующее исходной матрице,
        // наша последовательность шагов не минимальна        // (мы могли эту последовательность и не делать)
        // поэтому пропускаем дальнейшее рассмотрение этой цепочки шагов;
        // также мы можем не продолжать цепочку, если она длиннее какой-либо
        // другой цепочки шагов, которая даёт аткой же вариант матрицы;
        // иначе заходим внутрь if

                // check number of paths we arrived to this number mbit
                if (mbit!=firstBit // полученная матрица 
                              //не должа получиться, как исходная
// И мы ещё ни разу не получали такой вариант матрицы ЛИБО
// этот вариант мы получали более длинным способом
&& (path[mbit]==0 || path[mbit]>path[curBit]+1)
) {
// полученная матрица полученная из предыдущей + 1 шаг
                    path[mbit] = path[curBit] + 1;
                    // мы получили 0-матрицу? 
                    // вернем число шагов для получения 0-матрицы
                    // оно будет минимальным по построению
                    if ((mbit^0) == 0) return path[0];
                     // иначе полученную версию матрицы ставим в очередь
                    q.add(mbit);
                } 
                
                // возвращаемся к исходному состоянию матрицы
                m = flip(m, i, j); // return m to original state
            }
        }
    }
     // мы не вышли из алгоритма до сих пор и в очереди пусто,     // значит, решения не существует
    return -1;
}

// конвертируем бинарную матрицу в двоичное число
private int mat2bit (int[][]mat) {
    int res = 0;
    for (int i = 0; i < mat.length; i++) {
        for (int j = 0; j < mat[i].length; j++) {
            res = res * 2 + mat[i][j];
        }
    }
    return res;
}

// конвертируем двоичное число в бинарную матрицу с размером height х width
private int[][]bit2mat(int num, int height, int width) {
    int res[][] = new int[height][width];
    for (int i = height-1; i>=0; i--) {
        for (int j = width-1; j>=0; j--) {
            res[i][j] = (int)num % 2;
            num = num/2;
        }
    }
    return res;
}

// инвертируем ячейку(i,j) и её соседей
private int[][] flip(int[][]mat, int i, int j) {
    mat[i][j] = mat[i][j] == 1 ? 0 : 1;
    if (i>0) mat[i-1][j] = mat[i-1][j]==1 ? 0 : 1;
    if (i<mat.length-1) mat[i+1][j] = mat[i+1][j] == 1 ? 0 : 1;
    if (j>0) mat[i][j-1] = mat[i][j-1] == 1 ? 0 : 1;
    if (j<mat[i].length-1) mat[i][j+1] = mat[i][j+1] == 1 ? 0 : 1;
    return mat;
}

// вспомогательный метод, если захотим распечатать матрицу
// и посмотреть, что у нас получилось
private void printMatrix(int[][]matrix) {
    for (int i = 0; i < matrix.length; i++) {         
     for (int j = 0; j < matrix[i].length; j++) {  
        System.out.print(matrix[i][j] + " ");
     }
     System.out.println(); //change line on console as row comes to end in the matrix.
  }
}

Результаты теста:
Runtime: 2 ms, faster than 87.07% of Java online submissions for Minimum Number of Flips to Convert Binary Matrix to Zero Matrix.
Memory Usage: 39.8 MB, less than 100.00% of Java online submissions for Minimum Number of Flips to Convert Binary Matrix to Zero Matrix.