1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

use bit

T: O((mn)^2)
S: O(mn)

class Solution {
    public int minFlips(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;

        int res = Integer.MAX_VALUE;
        for (int state = 0; state < (1 << (m*n)); state++) { // state is bit representation(means flips ways)
            if (check(mat, state)) {
                res = Math.min(res, Integer.bitCount(state));
            }
        }
        return res == Integer.MAX_VALUE ? - 1 : res;
    }
    private boolean check(int[][] mat, int state) {
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0},{0,0}};
        
        int m = mat.length;
        int n = mat[0].length;
        int temp[][] = new int[m][n];
        
        for (int i = 0; i < m; i++) { // clone() only for 1d array (deep copy)
            temp[i] = mat[i].clone();
        }

        for (int b = 0; b < (m*n); b++) {
            int doFlip = state%2;
            state /= 2; // move to higher bit
            
            if (doFlip == 0) {
                continue;
            }
            
            int x = b/n;
            int y = b%n;
            for (int[] dir : dirs) {
                int nextX = x + dir[0];
                int nextY = y + dir[1];
                if (!isVaild(m, n, nextX, nextY)) {
                    continue;
                }            
                temp[nextX][nextY] = 1 - temp[nextX][nextY];
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (temp[i][j] != 0) {
                    return false;
                }
            }
        }
        return true;
    }
    private boolean isVaild(int m, int n, int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}

/*
1 <= m, n <= 3
3*3 matrix -> 9 elements
so the result is at most 2^9 = 512

use brute force:
so we can use bit to represent the all flip combinations

use these all flip combinations to flip (5 ways, include not flip) => T: O(mn)
if this combination can work, cal this combination's one, it's the flip numbers

find the min of (these flip numbers)

if it's a 2*2 matrix
ex:
[[0,0],[0,1]]

all flip combinations (是否要翻轉的所有方式)
can represent as
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

2. check method()
so when we use one flip to check , at last check is the result all zero, 
return true, if not return false

use one flip way to check

for all x, y cordination { // int b

ex: 
for (b = 0, b < mn; b++) // mn also 4, => T: O(mn)

0010, means first one doesn't flip, so skip : 
how to get lowest bits? (0010%2) is the lowest value of binary

(0010/2), move to higher next bit

001, means need to do flip

so check
int x = b/n
int y = b%n
check 5 dir
if (valid) {
 make temp[newX][newY] = 1 - temp[newX][newY]
}

3.
at last check all temp value is all zero => T: O(mn)

T: O((mn)^2)
S: O(mn)

*/