Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

Problem Id: 1284 Difficulty: Hard Tag: Breadth-first Search Tag: Graph


Intuition

We had been given in the constraints that 1 <= m <= 3 and 1 <= n <= 3. So there are at most 9 nodes. And over all 2 ** 9 different status.

Each status could be thought as a vertex in a graph. 2 vertices p, q, are connected when we flip one node in p, it becomes q.

So the problem becaumes to calculate the minimum path from the given mat to an all zero matrix.

Solution


import collections


class Solution:
    def index(self, mat):
        ans = 0
        for row in mat:
            for v in row:
                ans = (ans << 1) + v
        return ans

    def get_mat(self, index, m, n):
        ans = [[0] * n for _ in range(m)]
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                ans[i][j] = index % 2
                index = index >> 1
        return ans

    def convert(self, mat, i, j):
        for x, y in [(i, j), (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if 0 <= x < len(mat) and 0 <= y < len(mat[0]):
                mat[x][y] = 1 - mat[x][y]

    def minFlips(self, mat):
        m = len(mat)
        n = len(mat[0])
        visited = [-1] * (2 ** 9)
        visited[self.index(mat)] = 0
        queue = collections.deque([self.index(mat)])

        while queue:
            vertex = queue.popleft()
            mat = self.get_mat(vertex, m, n)
            for i in range(m):
                for j in range(n):
                    self.convert(mat, i, j)
                    child = self.index(mat)
                    if visited[child] == -1:
                        visited[child] = visited[vertex] + 1
                        queue.append(child)
                    self.convert(mat, i, j)
        return visited[0]