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

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

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

A zero matrix is a matrix with all cells equal to 0.

&nbsp;
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 do not need to change it.


Example 3:

Input: mat = [[1,0,0],[1,0,0]]
Output: -1
Explanation: Given matrix cannot be a zero matrix.


&nbsp;
Constraints:


	m == mat.length
	n == mat[i].length
	1 &lt;= m, n &lt;= 3
	mat[i][j] is either 0 or 1.


class Solution:
    flips = [11, 23, 38, 89, 186, 308, 200, 464, 416]
    
    def minFlips(self, mat: List[List[int]]) -> int:
        mask = self.make_mask(mat)
        check = self.make_mask([[1 for c in r] for r in mat])
        min_steps = -1
        last = 0
        for x in range(2**9):
            x = x & check
            flips = last ^ x
            last = x
            if not flips:
                continue
            for i in range(len(mat)):
                for j in range(len(mat[0])):
                    index = (i * 3 + j)
                    if 1 << index & flips:
                        mask ^= self.flips[index]
            if check & ~mask == check:
                steps = self.count_bits(x & check)
                if min_steps < 0 or steps < min_steps:
                    min_steps = steps
        return min_steps
    
    def make_mask(self, mat):
        d = 0
        for i in range(3):
            for j in range(3):
                if i < len(mat) and j < len(mat[0]):
                    d |= mat[i][j] << (i * 3 + j)
        return d

    def count_bits(self, x):
        count = 0
        i = 1
        while i <= x:
            count += int(bool(x & i))
            i <<= 1
        return count
class Solution {
    public int minFlips(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        int steps = 0;
        
        int initialState = toBinary(mat);
        queue.add(initialState);
        visited.add(initialState);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            
            for (int i = 0; i < size; i++) {
                int state = queue.poll();
                if (state == 0) return steps;
                int mask = 1;

                for (int y = 0; y < m; y++) {
                    for (int x = 0; x < n; x++) {
                        int nextState = flip(state, x, y, n, m);
                        if (!visited.contains(nextState)) {
                            visited.add(nextState);
                            queue.add(nextState);
                        }
                        mask = mask << 1;
                    }
                }
            }
            steps++;
        }
        return -1;
    }
    
    private int toBinary(int[][] M) {
        int bin = 0;
        for (int y = 0; y < M.length; y++) {
            for (int x = 0; x < M[0].length; x++) {
                bin = (bin << 1) + M[y][x];
            }
        }
        return bin;
    }
    
    private int flip(int state, int x, int y, int n, int m) {
        int flip = 1 << ((y*n) + x);
        flip += (x > 0) ? 1 << ((y*n) + (x-1)) : 0;
        flip += (x < n-1) ? 1 << ((y*n) + (x+1)) : 0;
        flip += (y > 0) ? 1 << (((y-1)*n) + x) : 0;
        flip += (y < m-1) ? 1 << (((y+1)*n) + x) : 0;
        return state ^ flip;
    }
}
class Solution {
public:
    bool check(string str) {
        for(auto &i: str)
            if(i=='1')
                return false;
        return true;
    }
    int minFlips(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        string str = "";
        for(auto &i: mat) {
            for(auto &j: i)
                str+=(j+'0');
        }
        
        unordered_set<string> st;
        queue<pair<string,int>> q;
        q.push({str,0});
        int steps = 0;
        
        while(q.size()) {
            string top = q.front().first;
            int step = q.front().second;
            if(check(top)) {
                    return step;
            }
            
            q.pop();
            steps++;
            for(int i=0; i<top.size(); ++i) {
                string temp = top;
                int x = i/n;
                int y = i%n;
                
                
                temp[i] = !(temp[i] - '0') + '0';
                if(x+1<m)
                    temp[y + (x+1)*n] = !(temp[y + (x+1)*n] - '0') + '0';
                if(x-1>=0)
                    temp[y + (x-1)*n] = !(temp[y + (x-1)*n] - '0') + '0';
                if(y+1<n)
                    temp[(y+1) + (x)*n] = !(temp[(y+1) + (x)*n] - '0') + '0';
                if(y-1>=0)
                    temp[(y-1) + (x)*n] = !(temp[(y-1) + (x)*n] - '0') + '0';
                
                // cout<<i<<" : "<<temp<<" "<<step+1<<endl;
                if(st.count(temp)==0) {
                    q.push({temp,step+1});
                    st.insert(temp);
                }
                
                
                if(check(temp)) {
                    return step+1;
                }
                
            }
            
        }
        return -1;
        
    }
};
// Helper counts how many ones are in the matrix to start with. O(mn)
var countOnes = function(mat) {
    let count = 0;
    for (let r = 0; r < mat.length; r++) {
        count += mat[r].reduce((a, b) => a + b);
    }
    return count;
}

// Helper flips a cell and its neighbors. Returns updated number of ones left in matrix. O(1)
var flip = function(mat, r, c, numOnes) {
    const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0], [0, 0]];
    dirs.forEach(el => {
        let newR = r + el[0], newC = c + el[1];
        if (newR >= 0 && newR < mat.length && newC >= 0 && newC < mat[0].length) {
            if (mat[newR][newC] === 0) {
                mat[newR][newC] = 1;
                numOnes++;
            } else {
                mat[newR][newC] = 0;
                numOnes--;
            }
        }
    })
    return numOnes;
}

// Main function tries every possible combination of cells being flipped using backtracking. O (2^(mn))
var minFlips = function(mat) {
    const rows = mat.length, cols = mat[0].length;
    let minFlips = Infinity, numOnes = countOnes(mat);
    
    var backtrackFlip = function(cell, flips) {
        if (numOnes === 0) minFlips = Math.min(minFlips, flips);
        for (let newCell = cell; newCell < rows * cols; newCell++) {
			// Function uses a cell number instead of row / col to keep track of column flips
			// For example, a 2 x 2 grid has cells "0", "1", "2", "3" and the line below calculates row / col based on that number
            const r = Math.floor(newCell / cols), c = newCell % cols;
            numOnes = flip(mat, r, c, numOnes);
            backtrackFlip(newCell + 1, flips + 1);
            numOnes = flip(mat, r, c, numOnes);
        }
    }
    
    backtrackFlip(0, 0);
    return minFlips === Infinity ? -1 : minFlips;
    
};
Minimum Number of Flips to Convert Binary Matrix to Zero Matrix