问题描述

给你一个 m x n 的二进制矩阵 mat。

每一步，你可以选择一个单元格并将它反转（反转表示 0 变 1 ，1 变 0 ）。如果存在和它相邻的单元格，那么这些相邻的单元格也会被反转。（注：相邻的两个单元格共享同一条边。）

请你返回将矩阵 mat 转化为全零矩阵的最少反转次数，如果无法转化为全零矩阵，请返回 -1 。

二进制矩阵的每一个格子要么是 0 要么是 1 。

全零矩阵是所有格子都为 0 的矩阵。

示例 1：

输入：mat = [[0,0],[0,1]]
输出：3
解释：一个可能的解是反转 (1, 0)，然后 (0, 1) ，最后是 (1, 1) 。

示例 2：

输入：mat = [[0]]
输出：0
解释：给出的矩阵是全零矩阵，所以你不需要改变它。

示例 3：

输入：mat = [[1,1,1],[1,0,1],[0,0,0]]
输出：6

示例 4：

输入：mat = [[1,0,0],[1,0,0]]
输出：-1
解释：该矩阵无法转变成全零矩阵

提示：

• m == mat.length
• n == mat[0].length
• 1 <= m <= 3
• 1 <= n <= 3
• mat[i][j] 是 0 或 1 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

请参考：滑动谜题

Python 实现

class Solution(object):
    def minFlips(self, mat):
        """
        :type mat: List[List[int]]
        :rtype: int
        """
        m, n, mat = len(mat), len(mat[0]), "".join(["".join(map(str, row)) for row in mat])
        result = "0" * (m * n)
        duplicate = set()
        queue = [(mat, 0)]
        while queue:
            mat, count = queue.pop(0)
            if mat == result:
                return count
            for child in self.get_children(mat, m, n):
                if child in duplicate:
                    continue
                duplicate.add(child)
                queue.append((child, count + 1))
        else:
            return -1

    def get_children(self, mat, m, n):
        for ind in range(len(mat)):
            row = ind / n
            column = ind % n

            # convert ind first
            s = mat[:ind] + self.convert(mat[ind]) + mat[ind+1:]
            left = self.get_left(column, ind)
            if left != -1:
                s = s[:left] + self.convert(mat[left]) + s[left+1:]
            right = self.get_right(column, ind, n)
            if right != -1:
                s = s[:right] + self.convert(mat[right]) + s[right+1:]
            up = self.get_up(row, ind, n)
            if up != -1:
                s = s[:up] + self.convert(mat[up]) + s[up+1:]
            down = self.get_down(row, ind, m, n)
            if down != -1:
                s = s[:down] + self.convert(mat[down]) + s[down+1:]

            yield s

    def convert(self, v):
        if v == "1":
            return "0"
        return "1"

    def get_left(self, column, ind):
        if column == 0:
            return -1
        return ind - 1

    def get_right(self, column, ind, n):
        if column == n - 1:
            return -1
        return ind + 1

    def get_up(self, row, ind, n):
        if row == 0:
            return -1
        return ind - n

    def get_down(self, row, ind, m, n):
        if row == m - 1:
            return -1
        return ind + n