diff options
Diffstat (limited to 'max_num_flips_binary_matrix.py')
-rw-r--r-- | max_num_flips_binary_matrix.py | 42 |
1 files changed, 42 insertions, 0 deletions
diff --git a/max_num_flips_binary_matrix.py b/max_num_flips_binary_matrix.py new file mode 100644 index 0000000..a29caa0 --- /dev/null +++ b/max_num_flips_binary_matrix.py @@ -0,0 +1,42 @@ +# 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]])) |