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

Key observations needed to solve this prob are as below.

1) There is no need to push the same button twice, as it doesn't make any change.

2) Sequence of buttons doesn't matter. In the provided example, a possible solution was (1,0)->(0,1)->(1,1). However, any sequences of the three buttons produce the same result.

 

Functions we need:

1) isComplete(): checks whether matrix only has zeros or not

2) push(button): pushes the button(int). Here, we use ^ (XOR) operation. (using the fact that 1 ^ 1 = 0 and 1 ^ 0 = 1)

 

Finally: DFS to go through all the cases

 

Time complexity is O(9 * 2**9). That is becasue we have 2**(M*N) cases, and we have to check M*N cells in each case where M, N <= 3.

* # of cases: XC0 + XC1 + XC2 + ... + XCX = 2**X, where X=M*N

 

class Solution:
    def minFlips(self, mat: List[List[int]]) -> int:
        self.mat = mat
        m, n = len(self.mat), len(self.mat[0])
        buttons = [i for i in range(m*n)]
        self.ret = 10
        self.dfs(buttons, [])
        return self.ret if self.ret != 10 else -1
        
    def dfs(self, buttons, visited):
        if self.isComplete():
            self.ret = min(self.ret, len(visited))
            return
        for i, button in enumerate(buttons):
            self.push(button)
            self.dfs(buttons[i+1:], visited+[button])
            self.push(button)
        
    def isComplete(self):
        m, n = len(self.mat), len(self.mat[0])
        for y in range(m):
            for x in range(n):
                if self.mat[y][x] != 0:
                    return False
        return True
    
    def push(self, button):
        m, n = len(self.mat), len(self.mat[0])
        y, x = button // n, button - button // n * n
        self.mat[y][x] ^= 1
        dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
        for d in range(4):
            next_y, next_x = y + dy[d], x + dx[d]
            if 0 <= next_y < m and 0 <= next_x < n:
                self.mat[next_y][next_x] ^= 1