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

BFS

T: O(m*n + 2^(m*n)), 1 <= m, n <= 3
S: 2^(m*n)

class Solution {
    private static final int[][] DIRS = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    private record Step(int state, int level){};
    public int minFlips(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;

        int state = 0;
        for (int i = m -1 ; i >= 0; i--) { // [0,0], [0,1] -> become 1000 -> 8
            for (int j = n - 1; j >= 0; j--) {
                state <<= 1; // left shift to have space
                state |= mat[i][j]; // set value, so the first value will be in left side, but we start from end, so [0,0] will be in most right side
            }
        }
        // System.out.println(state);

        Set<Integer> visited = new HashSet<>();
        Queue<Step> queue = new LinkedList<>();
        queue.offer(new Step(state, 0));

        while (!queue.isEmpty()) {
            Step cur = queue.poll();
            if (visited.contains(cur.state)) {
                continue;
            }
            visited.add(cur.state);
            if (cur.state == 0) {
                return cur.level;
            }
            // try each cell to do flip
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // flip this cell
                    int newState = cur.state;
                    int mask = 1 << (i*n + j); // move to that cell's position
                    newState ^= mask;

                    // then flip this cell's neights value
                    for (int[] dir: DIRS) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x < 0 || x >= m || y < 0 || y >= n) {
                            continue;
                        }
                        mask = 1 << (x*n + y);
                        newState ^= mask;

                    }
                    // after flip values, go to next round
                    queue.offer(new Step(newState, cur.level+1));
                }
            }
        }

        return -1;
    }
}
/**
state: 2^(m*n) 
so 
T: O(m*n + 2^(m*n)), 1 <= m, n <= 3
S: 2^(m*n)

 */

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)

*/