Minimum Number of Flips to Convert Binary Matrix to Zero Matrix LeetCode solution in Python

1
class Solution:
2
    flips = [11, 23, 38, 89, 186, 308, 200, 464, 416]
3

4
    def minFlips(self, mat: List[List[int]]) -> int:
5
        mask = self.make_mask(mat)
6
        check = self.make_mask([[1 for c in r] for r in mat])
7
        min_steps = -1
8
        last = 0
9
        for x in range(2**9):
10
            x = x & check
11
            flips = last ^ x
12
            last = x
13
            if not flips:
14
                continue
15
            for i in range(len(mat)):
16
                for j in range(len(mat[0])):
17
                    index = i * 3 + j
18
                    if 1 << index & flips:
19
                        mask ^= self.flips[index]
20
            if check & ~mask == check:
21
                steps = self.count_bits(x & check)
22
                if min_steps < 0 or steps < min_steps:
23
                    min_steps = steps
24
        return min_steps
25

26
    def make_mask(self, mat):
27
        d = 0
28
        for i in range(3):
29
            for j in range(3):
30
                if i < len(mat) and j < len(mat[0]):
31
                    d |= mat[i][j] << (i * 3 + j)
32
        return d
33

34
    def count_bits(self, x):
35
        count = 0
36
        i = 1
37
        while i <= x:
38
            count += int(bool(x & i))
39
            i <<= 1
40
        return count