Hard
题目描述
给定一个 m x n 的二进制矩阵 mat。在一步操作中，你可以选择一个单元格并翻转它以及它的四个相邻单元格（如果存在的话）。翻转的意思是将 1 变成 0，将 0 变成 1。两个单元格如果共享一条边，则称它们为相邻单元格。
返回将 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,0,0],[1,0,0]]
输出：-1
解释：给定的矩阵无法转换为零矩阵。
约束条件：
m == mat.lengthn == mat[i].length1 <= m, n <= 3mat[i][j]为0或1
提示：
- 翻转同一个位置两次等于没有翻转。每个位置最多只需要翻转一次。尝试所有可能的组合。时间复杂度 O(2^(n*m))。
解题思路
这道题有两种主要解法：暴力枚举和BFS。
方法一：暴力枚举（推荐）
根据题目提示，翻转同一个位置两次等于没有翻转，所以每个位置最多只需要翻转一次。对于 m×n 的矩阵，我们有 2^(m×n) 种翻转组合。
我们可以用一个整数的二进制表示来表示翻转方案，第 i 位为 1 表示翻转第 i 个位置。对于每种翻转方案，我们模拟执行翻转操作，检查最终是否能得到零矩阵。
翻转操作会影响当前位置及其上下左右四个相邻位置（如果存在）。
方法二：BFS
将矩阵状态看作一个节点，用 BFS 搜索从初始状态到零矩阵状态的最短路径。矩阵状态可以用整数编码，便于去重。
由于约束条件限制了矩阵大小最大为 3×3，状态空间不超过 2^9 = 512，所以两种方法都是可行的。暴力枚举实现更简单，推荐使用。
代码实现
class Solution {
public:
int minFlips(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
int total = m * n;
int ans = INT_MAX;
// 枚举所有可能的翻转组合
for (int mask = 0; mask < (1 << total); mask++) {
// 复制原矩阵
vector<vector<int>> grid = mat;
// 根据mask执行翻转操作
for (int i = 0; i < total; i++) {
if (mask & (1 << i)) {
int row = i / n, col = i % n;
flip(grid, row, col, m, n);
}
}
// 检查是否为零矩阵
if (isZeroMatrix(grid)) {
ans = min(ans, __builtin_popcount(mask));
}
}
return ans == INT_MAX ? -1 : ans;
}
private:
void flip(vector<vector<int>>& grid, int r, int c, int m, int n) {
int dirs[5][2] = {{0, 0}, {-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int i = 0; i < 5; i++) {
int nr = r + dirs[i][0], nc = c + dirs[i][1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
grid[nr][nc] ^= 1;
}
}
}
bool isZeroMatrix(const vector<vector<int>>& grid) {
for (const auto& row : grid) {
for (int val : row) {
if (val == 1) return false;
}
}
return true;
}
};
class Solution:
def minFlips(self, mat: List[List[int]]) -> int:
m, n = len(mat), len(mat[0])
total = m * n
ans = float('inf')
# 枚举所有可能的翻转组合
for mask in range(1 << total):
# 复制原矩阵
grid = [row[:] for row in mat]
# 根据mask执行翻转操作
for i in range(total):
if mask & (1 << i):
row, col = i // n, i % n
self.flip(grid, row, col, m, n)
# 检查是否为零矩阵
if self.is_zero_matrix(grid):
ans = min(ans, bin(mask).count('1'))
return ans if ans != float('inf') else -1
def flip(self, grid, r, c, m, n):
dirs = [(0, 0), (-1, 0), (1, 0), (0, -1), (0, 1)]
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n:
grid[nr][nc] ^= 1
def is_zero_matrix(self, grid):
return all(val == 0 for row in grid for val in row)
public class Solution {
public int MinFlips(int[][] mat) {
int m = mat.Length, n = mat[0].Length;
int total = m * n;
int ans = int.MaxValue;
// 枚举所有可能的翻转组合
for (int mask = 0; mask < (1 << total); mask++) {
// 复制原矩阵
int[][] grid = new int[m][];
for (int i = 0; i < m; i++) {
grid[i] = new int[n];
Array.Copy(mat[i], grid[i], n);
}
// 根据mask执行翻转操作
for (int i = 0; i < total; i++) {
if ((mask & (1 << i)) != 0) {
int row = i / n, col = i % n;
Flip(grid, row, col, m, n);
}
}
// 检查是否为零矩阵
if (IsZeroMatrix(grid)) {
ans = Math.Min(ans, CountBits(mask));
}
}
return ans == int.MaxValue ? -1 : ans;
}
private void Flip(int[][] grid, int r, int c, int m, int n) {
int[,] dirs = {{0, 0}, {-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int i = 0; i < 5; i++) {
int nr = r + dirs[i, 0], nc = c + dirs[i, 1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
grid[nr][nc] ^= 1;
}
}
}
private bool IsZeroMatrix(int[][] grid) {
foreach (var row in grid) {
foreach (int val in row) {
if (val == 1) return false;
}
}
return true;
}
private int CountBits(int n) {
int count = 0;
while (n != 0) {
count++;
n &= n - 1;
}
return count;
}
}
var minFlips = function(mat) {
const m = mat.length;
const n = mat[0].length;
const matrixToState = (matrix) => {
let state = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 1) {
state |= (1 << (i * n + j));
}
}
}
return state;
};
const flip = (state, row, col) => {
const directions = [[0, 0], [-1, 0], [1, 0], [0, -1], [0, 1]];
for (const [dr, dc] of directions) {
const nr = row + dr;
const nc = col + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
state ^= (1 << (nr * n + nc));
}
}
return state;
};
const initialState = matrixToState(mat);
if (initialState === 0) return 0;
const queue = [initialState];
const visited = new Set([initialState]);
let steps = 0;
while (queue.length > 0) {
const size = queue.length;
steps++;
for (let i = 0; i < size; i++) {
const currentState = queue.shift();
for (let row = 0; row < m; row++) {
for (let col = 0; col < n; col++) {
const nextState = flip(currentState, row, col);
if (nextState === 0) return steps;
if (!visited.has(nextState)) {
visited.add(nextState);
queue.push(nextState);
}
}
}
}
}
return -1;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(2^(m×n) × m×n) | 枚举所有 2^(m×n) 种翻转组合，每次需要 O(m×n) 时间进行翻转和检查 |
| 空间复杂度 | O(m×n) | 需要复制矩阵进行模拟 |