题目描述
给一个二维矩阵，里面的元素不是0就是1
可以通过翻转完成0-1变换，翻转的限制是周围相邻的点也要跟着变
问最终反转成全0的形式的最小次数？
基本分析
- 看大最少翻转次数可以联想到什么？bfs
- 直接bfs有啥问题？（1）矩阵的形式怎么存？通过状态压缩将二维转化为1维度
- 要实现以上需求需要做什么？定义encode函数，将mat转化为x；因为枚举翻转点的时候，有需要在mat上操作，所以需要有函数将x解码为mat
- 翻转的逻辑？对需要翻转的点，将点和相邻点的值^1
- bfs怎么保证不重？对x_cur在入队的时候进行检查，不在vis中的才入队
- 对每个点进行枚举之后需要注意什么？因为是本地操作，需要还原现场
代码
class Solution:
def minFlips(self, mat: List[List[int]]) -> int:
def encode(mat, m, n):
x = 0
for i in range(m):
for j in range(n):
x = x * 2 + mat[i][j]
return x
def decode(x, m, n):
mat = [[0] * n for _ in range(m)]
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
mat[i][j] = x & 1
x = x >> 1
return mat
def convert(mat, m, n, i, j):
for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:
if 0 <= i + di < m and 0 <= j + dj < n:
mat[i + di][j + dj] ^= 1
m, n = len(mat), len(mat[0])
x_start = encode(mat, m, n)
if x_start == 0:
return 0
vis = {x_start}
step = 0
q = deque([x_start])
while q:
step += 1
for _ in range(len(q)):
mat = decode(q.popleft(), m, n)
for i in range(m):
for j in range(n):
convert(mat, m, n, i, j)
x_cur = encode(mat, m, n)
if x_cur == 0:
return step
if not x_cur in vis:
q.append(x_cur)
vis.add(x_cur)
convert(mat, m, n, i, j)
return -1
总结
- 将矩阵状态压缩为1维，这样矩阵的状态就可以去重和放进队列里面了
- 对点修改的时候需要考虑临近的点，这里对mat是本地操作，枚举每个修改的点之后需要还原现场
待完善