Leetcode 1284:转化为全零矩阵的最少反转次数(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1284:转化为全零矩阵的最少反转次数(超详细的解法!!!)

in leetcode with 0 comment

给你一个 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
解释:该矩阵无法转变成全零矩阵 

提示:

解题思路

实际上这个问题可以转化为图的最短路问题,题目中矩阵的最大边长是3,所以我们可以通过一个int变量表示矩阵的每一位变化(因为int32位,而矩阵最多9个值)。观察第一个例子,当前状态可以表示为1000(通过mat[i][j] << i*c + j计算得到,其中c表示矩阵的列数)

所以这个问题就转化为了最短路问题,使用bfs即可。

from functools import reduce
class Solution:
    def minFlips(self, mat: List[List[int]]) -> int:
        r, c = len(mat), len(mat[0])
        start = reduce(operator.ior, [t << i * c + j for i, row in enumerate(mat) for j, t in enumerate(row)])
        
        q = [(start, 0)]
        seen = set([start])
        while q:
            cur, step = q.pop(0)
            if not cur:
                return step
            for i in range(r):
                for j in range(c):
                    ne = cur
                    for x, y in (i, j), (i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j):
                        if x >= 0 and x < r and y >= 0 and y < c:
                            ne ^= 1 << x * c + y
                    if ne not in seen:
                        seen.add(ne)
                        q.append((ne, step + 1))
        return -1

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses