1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class Solution:
    def minFlips(self, mat: List[List[int]]) -> int:
        def toString(mat):
            return "".join(str(x) for x in sum(mat, []))
        def flip(mat, i, j):
            temp = deepcopy(mat)
            temp[i][j] ^= 1
            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                x, y = i + dx, j + dy
                if 0 <= x < m and 0 <= y < n:
                    temp[x][y] ^= 1
            return temp
        m, n = len(mat), len(mat[0])
        s = "0" * (m * n)
        s_mat = toString(mat)
        if s_mat == s:
            return 0
        q = [[0] * n for _ in range(m)](/TengnanYao/daily_leetcode/wiki/[0]-*-n-for-_-in-range(m))
        result = 0
        seen = {s}
        while q:
            arr = []
            for matrix in q:
                for i in range(m):
                    for j in range(n):
                        temp = flip(matrix, i, j)
                        t = toString(temp)
                        if t not in seen:
                            if t == s_mat:
                                return result + 1
                            seen.add(t)
                            arr.append(temp)
            q = arr
            result += 1
        return -1