# LeetCode: 1284. 转化为全零矩阵的最少反转次数¶

## 1、题目描述¶

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



输入：mat = [[0]]



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



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



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

## 2、解题思路¶

• 使用Dijkstra搜索
• 将数组编程一维的字符串用来表示 当前的数组
• 首先从初始状态开始，不断的找下一个状态，作为当前状态的下一个节点
• 然后使用Dijkstra算法搜索，找出到全0的最短路径
from typing import List
from collections import defaultdict
from collections import namedtuple
from functools import reduce
import heapq
from copy import deepcopy

EdgeNode = namedtuple("EdgeNode", ["weight", "node"])
PreEdgeNode = namedtuple("PreEdgeNode", ["weight", "node", "pre_node"])

class Dijkstra:
def __init__(self, edges, source):
inf = float('inf')
self.graph = edges
self.dis = {source: 0}
self.q = []

for weight, t in edges[source]:
heapq.heappush(self.q, PreEdgeNode(weight, t, source))

self._find_shortest()

def _find_shortest(self):
"""
使用dijkstra算法计算最短距离，并更新最短路径的前驱节点
:return:
"""
while self.q:
weight, node, pre_node = heapq.heappop(self.q)
if node in self.dis:
continue
self.dis[node] = weight
for next_node_weight, next_node in self.graph[node]:
if next_node not in self.dis:
heapq.heappush(self.q, PreEdgeNode(weight + next_node_weight, next_node, node))

def get_shortest_dis(self, target: int) -> int:
"""
返回距离source点的最短距离
:param target: 目标点
:return: 如果目标点不在图中，返回-1
"""
if target in self.dis:
return self.dis[target]
return -1

class Solution:
def minFlips(self, mat: List[List[int]]) -> int:

row, col = len(mat), len(mat[0])

target = "0" * (row * col)
func = lambda x: [y for l in x for y in func(l)] if type(x) is list else [x]
source = str(reduce(lambda x, y: str(x) + str(y), func(mat)))

edges = defaultdict(set)
# 上下左右-坐标
surround = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# 坐标验证
def available(m, n):
return 0 <= m < row and 0 <= n < col

def get_next_stat(current):
current_stat = str(reduce(lambda x, y: str(x) + str(y), func(current)))
if edges[current_stat]:
return
for i in range(row):
for j in range(col):
temp = deepcopy(current)
temp[i][j] = 0 if temp[i][j] == 1 else 1
for dx, dy in surround:
nx, ny = i + dx, j + dy
if available(nx, ny):
temp[nx][ny] = 0 if temp[nx][ny] == 1 else 1
temp_stat = str(reduce(lambda x, y: str(x) + str(y), func(temp)))