Leetcode 1409 Solution

This article provides solution to leetcode question 1409 (minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix)

https://leetcode.com/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix

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)

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)