# 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
"""
given an 'm x n' binary matrix 'mat'. in one step, you can choose one cell
and flip it and all the four neighbours of it if they exist (fip is changing
1 to 0, and 0 to 1). a pair ofcells are called neighbours if their share one
edge. return the minimum number of steps required to convert 'mat' to a zero
matrix or -1 if you cannot. a binary matrix isa matrix with all cells equal
to 0 or 1 only. a zero matrix is a matrix with all cells equal to 0.
"""
class Solution(object):
def minFlips(self, mat):
"""
:type mat: List[List[int]]
:rtype: int
"""
m, n = len(mat), len(mat[0])
start = sum(
cell << i * n + j for i, row in enumerate(mat) for j, cell in enumerate(row)
)
stack, seen = [(start, 0)], {start: 0}
while stack:
curr, step = stack.pop()
for i in range(m):
for j in range(n):
next = curr
for r, c in (i, j), (i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j):
if m > r >= 0 <= c < n:
next ^= 1 << r * n + c
if seen.get(next, float("inf")) > step + 1:
seen[next] = step + 1
stack.append((next, step + 1))
return seen.get(0, -1)
if __name__ == "__main__":
obj = Solution()
print(obj.minFlips(mat=[[0, 0], [0, 1]]))
print(obj.minFlips(mat=[[0]]))
print(obj.minFlips(mat=[[1, 0, 0], [1, 0, 0]]))
