aboutsummaryrefslogtreecommitdiff
path: root/max_num_flips_binary_matrix.py
blob: a29caa023aaa4bf64bb6457247734aba91a1c15e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

"""
given an 'm x n' binary matrix 'mat'. in one step, you can choose one cell
and flip it and all the four neighbours of it if they exist (fip is changing
1 to 0, and 0 to 1). a pair ofcells are called neighbours if their 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 isa matrix with all cells equal
to 0 or 1 only. a zero matrix is a matrix with all cells equal to 0.
"""


class Solution(object):
    def minFlips(self, mat):
        """
        :type mat: List[List[int]]
        :rtype: int
        """
        m, n = len(mat), len(mat[0])
        start = sum(
            cell << i * n + j for i, row in enumerate(mat) for j, cell in enumerate(row)
        )
        stack, seen = [(start, 0)], {start: 0}
        while stack:
            curr, step = stack.pop()
            for i in range(m):
                for j in range(n):
                    next = curr
                    for r, c in (i, j), (i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j):
                        if m > r >= 0 <= c < n:
                            next ^= 1 << r * n + c
                    if seen.get(next, float("inf")) > step + 1:
                        seen[next] = step + 1
                        stack.append((next, step + 1))
        return seen.get(0, -1)


if __name__ == "__main__":
    obj = Solution()
    print(obj.minFlips(mat=[[0, 0], [0, 1]]))
    print(obj.minFlips(mat=[[0]]))
    print(obj.minFlips(mat=[[1, 0, 0], [1, 0, 0]]))