Python BFS

It’s an interesting BFS problem. A little bit harder than regular ones, however, the solution is still very standard.

The problem is this week’s latest contest. It seems that Leetcode reduces the difficulties level of the contest in order to celebrate Christmas (only my guess). More than 700 people successfully solved all the 4 questions in the contest.

1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

The run time is 40 ms.

from collections import deque
class Solution:
    def minFlips(self, A: List[List[int]]) -> int:
        R, C = len(A), len(A[0])
        a = [str(A[i][j]) for i in range(R) for j in range(C)]
        a = ''.join(a)
        if a == '0'*(R*C):return 0 
        def bfs(a):
            flip = {'0':'1', '1':'0'}
            open_list = deque([(a, 0)])
            seen = {a}
            while open_list:
                state, d = open_list.popleft()
                for i in range(R):
                    for j in range(C):
                        valids = [(i+di, j+dj) for di, dj in [(0, 1),(0, -1),(1, 0),(-1, 0)] if 0<=i+di<R and 0<=j+dj<C]
                        state_l = list(state)
                        for ii, jj in valids+[(i, j)]:
                            idx = C*ii + jj
                            state_l[idx] = flip[state_l[idx]] 
                        state_new = ''.join(state_l)
                        if state_new == '0'*(R*C):return d+1
                        if state_new not in seen:
                            seen.add(state_new)
                            open_list.append((state_new, d+1))
            return -1
        return bfs(a)

Thanks.