Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

Given a m x n binary matrix mat. In one step, you can choose one cell and flip it and all the four neighbours of it if they exist (Flip is changing 1 to 0 and 0 to 1). A pair of cells are called neighboors if they share one edge.

Return the minimum number of steps required to convert mat to a zero matrix or -1 if you cannot.

Binary matrix is a matrix with all cells equal to 0 or 1 only.

Zero matrix is a matrix with all cells equal to 0.

 

Example 1:

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.
Example 2:

Input: mat = [[0]]
Output: 0
Explanation: Given matrix is a zero matrix. We don't need to change it.
Example 3:

Input: mat = [[1,1,1],[1,0,1],[0,0,0]]
Output: 6
Example 4:

Input: mat = [[1,0,0],[1,0,0]]
Output: -1
Explanation: Given matrix can't be a zero matrix
 

Constraints:


Solution:

class Solution {
    public int minFlips(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        List<List<Integer>> start = getM(mat);
        Deque<List<List<Integer>>> queue = new ArrayDeque();
        Set<List<List<Integer>>> visited = new HashSet();
        visited.add(start);
        queue.offer(start);
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i ++) {
                List<List<Integer>> curr = queue.poll();
                // System.out.println(curr);
                if (isAllZero(curr)) {
                    return step;
                }
                for (int j = 0; j < m; j ++) {
                    for (int k = 0; k < n; k ++) {
                        List<List<Integer>> next = update(curr, j, k);
                        if (visited.add(next)) {
                            queue.offer(next);
                        }
                    }
                }
            }
            step ++;
        }
        return -1;
    }
    
    private List<List<Integer>> getM(int[][] M) {
        int m = M.length, n = M[0].length;
        List<List<Integer>> target = new ArrayList();
        for (int i = 0; i < m; i ++) {
            List<Integer> row = new ArrayList();
            for (int j = 0; j < n; j ++) {
                row.add(M[i][j]);
            }
            target.add(row);
        }
        return target;
    }
    
    private boolean isAllZero(List<List<Integer>> M) {
        for (List<Integer> l : M) {
            for (int i : l) {
                if (i != 0) return false;
            }
        }
        return true;
    }
    
    private List<List<Integer>> update(List<List<Integer>> curr, int x, int y) {
        List<List<Integer>> res = new ArrayList();
        for (int i = 0; i < curr.size(); i ++) {
            List<Integer> row = new ArrayList();
            for (int j = 0; j < curr.get(0).size(); j ++) {
                int val = curr.get(i).get(j);
                if (i == x && j == y) {
                    val = 1 - val;
                } else if (Math.abs(i - x) + Math.abs(j - y) == 1) {
                    val = 1 - val;
                }
                row.add(val);
            }
            res.add(row);
        }
        return res;
    }
}