Problem statement

https://binarysearch.com/problems/Convert-Binary-Matrix-to-Zero-Matrix/

Solution

Equal to 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix, but we need to use more optimized solution to get AC.

Complexity

It is O(2^mn) for time and space.

Code

class Solution:
    def solve(self, mat):
        if not mat or not mat[0]: return 0

        n, m = len(mat), len(mat[0])
        mask = sum(x << i for i, x in enumerate(reduce(lambda a, b: b + a, mat)))

        def flip(i, j, mask):
            for r, c in [(i, j), (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
                if 0 <= r < n and 0 <= c < m:
                    mask ^= 1 << (r * m + c)
            return mask

        Q, V = deque([(0, mask)]), set([mask])

        while Q:
            cost, shape = Q.popleft()
            if not shape: return cost
            for i, j in product(range(n), range(m)):
                mask2 = flip(i, j, shape)
                if mask2 in V: continue
                V.add(mask2)
                Q.append((cost + 1, mask2))

        return -1