Leetcode 1409 Solution

class Solution:
    def minFlips(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])

        def flip(mat, i, j):
            nonlocal m
            nonlocal n

            new_mat = copy.deepcopy(mat)

            new_mat[i][j] = 1 - new_mat[i][j]
            for ni, nj in [
                (i, j + 1),
                (i + 1, j),
                (i - 1, j),
                (i, j - 1),
            ]:
                if not (0 <= ni < m and 0 <= nj < n):
                    continue

                new_mat[ni][nj] = 1 - new_mat[ni][nj]
            return new_mat

        def get_key(mat):
            return ":".join([",".join([str(v) for v in row]) for row in mat])

        def is_all_zero(mat):
            for row in mat:
                for v in row:
                    if v != 0:
                        return False
            return True

        q = collections.deque()
        visited = set()

        q.append(mat)
        visited.add(get_key(mat))

        step = 0
        while q:
            s = len(q)
            for _ in range(s):
                mat = q.popleft()

                if is_all_zero(mat):
                    return step

                for i in range(m):
                    for j in range(n):
                        new_mat = flip(mat, i, j)
                        new_mat_key = get_key(new_mat)
                        if new_mat_key in visited:
                            continue

                        q.append(new_mat)
                        visited.add(new_mat_key)

            step += 1

        return -1