golang 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2023-05-24 10:02:49

// bfs
func minFlips(mat [][]int) int {
    n, m := len(mat), len(mat[0])
    length := n * m

    dx := []int{1, 0, -1, 0}
    dy := []int{0, 1, 0, -1}

    // 二维转一维向量，用字符串存储
    ans := make([]byte, length)
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            ans[i * m + j] = byte(mat[i][j])
        }
    }
    root := string(ans)

    vis := map[string]int{}  // 矩阵 -> 翻转次数
    vis[root] = 0
    // bfs
    que := []string{root}
    for len(que) > 0 {
        s := que[0]
        que = que[1:]
        flag := false // 判断是否存在 1
        
        for i := 0; i < length; i++ {
            if s[i] == 1 { flag = true  }

            tmp := []byte(s)
            x, y := i / m, i % m
            // 反转自身及相邻单元格
            tmp[i] = 1 - tmp[i]
            for j := 0; j < 4; j++ {
                nx, ny := x + dx[j],  y + dy[j]
                if nx < 0 || nx >= n || ny < 0 || ny >= m {
                    continue
                }
                idx := nx * m + ny
                tmp[idx] = 1 - tmp[idx]
            }
            
            st := string(tmp)
            if _, ok := vis[st]; !ok {
                que = append(que, st)
                vis[st] = vis[s] + 1
            }
        }

        if !flag {
            return vis[s]
        }
    }
    
    return -1
}

python3 解法, 执行用时: 40 ms, 内存消耗: 15.9 MB, 提交时间: 2023-05-24 10:02:04

'''
状态回溯
由于每个点反转两次等于没有反转，所以每个点最多只会反转一次。
也就是说每个点只有反转与不反转两种选择，类似01背包。
采用状态压缩映射当前遍历点的横纵坐标（一共是m * n个点，可以用0 - m * n - 1来映射）
在回溯过程中，当所有点遍历完之后判断矩阵中是否有1，如果有的话返回inf，否则返回0.
当点未遍历完，寻找翻转当前点和不反转当前点的最小值即可。
'''
class Solution:
    def minFlips(self, mat: List[List[int]]) -> int:
        def stack(i, j):#以i，j为中心反转
            for x, y in [[i, j], [i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:
                if 0 <= x < m and 0 <= y < n:
                    mat[x][y] = 0 if mat[x][y] == 1 else 1
            
        def dfs(state):#状态位
            if state == m * n:#如果所有点遍历完了
                return 0 if sum(sum(i) for i in mat) == 0 else float("inf")#根据是否有1来决定返回0或者inf
            x, y = state // n, state % n#状态位转横纵坐标
            res = dfs(state + 1)#不反转的结果
            stack(x, y)#反转
            res = min(res, 1 + dfs(state + 1))#找到和反转后的最小值
            stack(x, y)#再次反转回溯
            return res

        m, n = len(mat), len(mat[0])
        res = dfs(0)
        return res if res < float("inf") else -1

python3 解法, 执行用时: 40 ms, 内存消耗: 15.9 MB, 提交时间: 2023-05-24 10:01:13

# dfs

class Solution:
    def __init__(self):
        self.ans = 10**9

    def convert(self, mat, m, n, i, j):
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:
            i0, j0 = i + di, j + dj
            if 0 <= i0 < m and 0 <= j0 < n:
                mat[i0][j0] ^= 1

    def dfs(self, mat, m, n, pos, flip_cnt):
        if pos == m * n:
            if all(mat[i][j] == 0 for i in range(m) for j in range(n)):
                self.ans = min(self.ans, flip_cnt)
            return

        x, y = pos // n, pos % n
        # not flip
        self.dfs(mat, m, n, pos + 1, flip_cnt)
        # flip
        self.convert(mat, m, n, x, y)
        self.dfs(mat, m, n, pos + 1, flip_cnt + 1)
        self.convert(mat, m, n, x, y)

    def minFlips(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        self.dfs(mat, m, n, 0, 0)
        return self.ans if self.ans != 10**9 else -1

python3 解法, 执行用时: 76 ms, 内存消耗: 16.3 MB, 提交时间: 2023-05-24 10:00:39

# bfs
import queue

class Solution:
    def encode(self, 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(self, 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 >>= 1
        return mat

    def convert(self, mat, m, n, i, j):
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:
            i0, j0 = i + di, j + dj
            if 0 <= i0 < m and 0 <= j0 < n:
                mat[i0][j0] ^= 1

    def minFlips(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        x_start, step = self.encode(mat, m, n), 0
        if x_start == 0:
            return step

        visited = {x_start}
        q = queue.Queue()
        q.put_nowait(x_start)

        while not q.empty():
            step += 1
            k = q.qsize()
            for _ in range(k):
                status = self.decode(q.get_nowait(), m, n)
                for i in range(m):
                    for j in range(n):
                        self.convert(status, m, n, i, j)
                        x_cur = self.encode(status, m, n)
                        if x_cur == 0:
                            return step
                        if x_cur not in visited:
                            visited.add(x_cur)
                            q.put_nowait(x_cur)
                        self.convert(status, m, n, i, j)

        return -1