1284. 转化为全零矩阵的最少反转次数（Rating 1810）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

1284. 转化为全零矩阵的最少反转次数

Rating 1810

思路

类似最少xx次数的题目，如果能将每个状态建模为图的节点，各状态间的变换建模为图中节点之间权值为1的边，那么即可通过bfs求得结果。

本题则是需要维护一个mat翻转前后的状态。

矩阵本身并不好hash，因此考虑将矩阵编码为独一无二的状态。

因为mat中非0即1，通过位运算编码则是比较直观的一个思路。

代码

import collections

class Solution:
    def minFlips(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])

        def mat2num(mat: List[List[int]]) -> int: # 将矩阵编码为数字
            num = 0
            for i in range(m):
                for j in range(n):
                    num = (num << 1) + mat[i][j] # 通过位运算实现编码
            return num

        def num2mat(num: int) -> List[List[int]]: # 将数字解码为矩阵
            mat = [[0 for _ in range(n)] for _ in range(m)]
            for i in range(m - 1, -1, -1):
                for j in range(n - 1, -1, -1):
                    mat[i][j] = (num & 1) # 通过位运算实现解码
                    num = (num >> 1)
            return mat
        
        dir = [-1, 0, 1, 0, -1] # 上下左右四个方向list
        state = mat2num(mat) # mat初始状态的编码值
        q = collections.deque() # 经典bfs模板
        q.append(state)
        vis = set()
        vis.add(state)
        ret = 0
        while q:
            sz = len(q)
            while sz:
                sz -= 1
                s = q.popleft()
                if s == 0: # 全0，则得到了目标状态
                    return ret
                mt = num2mat(s) # 解码当前bfs的状态
                for i in range(m): # 遍历所有可以翻转的部份
                    for j in range(n):
                        mt[i][j] = 1 - mt[i][j] # 翻转当前位置
                        for k in range(4): # 翻转上下左右位置
                            x = i + dir[k]
                            y = j + dir[k + 1]
                            if x < 0 or x >= m or y < 0 or y >= n: # 越界保护
                                continue
                            mt[x][y] = 1 - mt[x][y]
                        nxts = mat2num(mt) # 得到翻转后的编码值，如果没有见过则加入队列
                        if nxts not in vis:
                            q.append(nxts)
                            vis.add(nxts)
                        for k in range(4): # 因为还要遍历下一个位置，所以要翻转回去
                            x = i + dir[k]
                            y = j + dir[k + 1]
                            if x < 0 or x >= m or y < 0 or y >= n:
                                continue
                            mt[x][y] = 1 - mt[x][y]
                        mt[i][j] = 1 - mt[i][j] # 翻转回去
            ret += 1
        return -1 # 没找到目标状态，返回-1