题目：转化为全零矩阵的最少反转次数
给你一个m x n的二进制矩阵mat。每一步，你可以选择一个单元格并将它反转（反转表示0变1，1变0）。如果存在和它相邻的单元格，那么这些相邻的单元格也会被反转。相邻的两个单元格共享同一条边。
请你返回将矩阵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.length
•n == mat[0].length
•  1 <= m <= 3
•  1 <= n <= 3
•mat[i][j]是 0 或 1 。
语言:C++
class Solution {
private:
static constexpr int dirs[5][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {0, 0}};
public:
int encode(const vector<vector<int>>& mat, int m, int n) {
int x = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
x = x * 2 + mat[i][j];
}
}
return x;
}
vector<vector<int>> decode(int x, int m, int n) {
vector<vector<int>> mat(m, vector<int>(n));
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
mat[i][j] = x & 1;
x >>= 1;
}
}
return mat;
}
void convert(vector<vector<int>>& mat, int m, int n, int i, int j) {
for (int k = 0; k < 5; ++k) {
int i0 = i + dirs[k][0], j0 = j + dirs[k][1];
if (i0 >= 0 && i0 < m && j0 >= 0 && j0 < n) {
mat[i0][j0] ^= 1;
}
}
}
int minFlips(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
int x_start = encode(mat, m, n), step = 0;
if (x_start == 0) {
return step;
}
unordered_set<int> visited;
queue<int> q;
visited.insert(x_start);
q.push(x_start);
while (!q.empty()) {
++step;
int k = q.size();
for (int _ = 0; _ < k; ++_) {
vector<vector<int>> status = decode(q.front(), m, n);
q.pop();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
convert(status, m, n, i, j);
int x_cur = encode(status, m, n);
if (x_cur == 0) {
return step;
}
if (!unt(x_cur)) {
visited.insert(x_cur);
q.push(x_cur);
}
convert(status, m, n, i, j);
}
}
}
}
return -1;
}
};
语言:C++
class Solution {
private:
static constexpr int dirs[5][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {0, 0}}; int ans;
public:
Solution(): ans(1e9) {
}
void convert(vector<vector<int>>& mat, int m, int n, int i, int j) {
for (int k = 0; k < 5; ++k) {
int i0 = i + dirs[k][0], j0 = j + dirs[k][1];
if (i0 >= 0 && i0 < m && j0 >= 0 && j0 < n) {
mat[i0][j0] ^= 1;
}
}
}
void dfs(vector<vector<int>>& mat, int m, int n, int pos, int flip_cnt) { if (pos == m * n) {
bool flag = true;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (mat[i][j] != 0) {
flag = false;
}
}
}
if (flag) {
ans = min(ans, flip_cnt);
}
return;
}
int x = pos / n, y = pos % n;
// not flip
dfs(mat, m, n, pos + 1, flip_cnt);
// flip
convert(mat, m, n, x, y);
dfs(mat, m, n, pos + 1, flip_cnt + 1);
convert(mat, m, n, x, y);
}
int minFlips(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
dfs(mat, m, n, 0, 0);
return (ans != 1e9 ? ans : -1);
}
};
语言:C++
class Solution {
private:
static constexpr int dirs[5][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {0, 0}}; int ans;
public:
Solution(): ans(1e9) {
}
void convert(vector<vector<int>>& mat, int m, int n, int i, int j) {
for (int k = 0; k < 5; ++k) {
int i0 = i + dirs[k][0], j0 = j + dirs[k][1];
if (i0 >= 0 && i0 < m && j0 >= 0 && j0 < n) {
mat[i0][j0] ^= 1;
}
}
}
void dfs(vector<vector<int>>& mat, int m, int n, int pos, int flip_cnt) { if (pos == m * n) {
bool flag = true;
for (int j = 0; j < n; ++j) {
if (mat[m - 1][j] != 0) {
flag = false;
break;
}
}
if (flag) {
ans = min(ans, flip_cnt);
}
return;
}
int x = pos / n, y = pos % n;
if (x == 0) {
// in the first line we can choose either flip or not flip
// not flip
dfs(mat, m, n, pos + 1, flip_cnt);
// flip
convert(mat, m, n, x, y);
dfs(mat, m, n, pos + 1, flip_cnt + 1);
convert(mat, m, n, x, y);
}
else {
// otherwise it depends on the upper grid
if (mat[x - 1][y] == 0) {
dfs(mat, m, n, pos + 1, flip_cnt);
}
else {
convert(mat, m, n, x, y);
dfs(mat, m, n, pos + 1, flip_cnt + 1);
convert(mat, m, n, x, y);
}
}
}
int minFlips(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
dfs(mat, m, n, 0, 0);
return (ans != 1e9 ? ans : -1);
}
};
语言:Python
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
if0<= i0 < m and0<= j0 < n:
mat[i0][j0] ^=1

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。