# 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

Given a `m x n` binary matrix `mat`. In one step, you can choose one cell and flip it and all the four neighbors of it if they exist (Flip is changing `1` to `0` and `0` to `1`). A pair of cells are called neighbors if they share one edge.

Return the  minimum number of steps  required to convert `mat` to a zero matrix or `-1` if you cannot.

A binary matrix is a matrix with all cells equal to `0` or `1` only.

A zero matrix is a matrix with all cells equal to `0`.

Example 1:

``````Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.
``````

Example 2:

``````Input: mat = [[0]]
Output: 0
Explanation: Given matrix is a zero matrix. We do not need to change it.
``````

Example 3:

``````Input: mat = [[1,0,0],[1,0,0]]
Output: -1
Explanation: Given matrix cannot be a zero matrix.
``````

Constraints:

• `m == mat.length`
• `n == mat[i].length`
• `1 <= m, n <= 3`
• `mat[i][j]` is either `0` or `1`.

``````class Solution {
public:
int minFlips(vector<vector<int>>& mat) {
int res = 0, m = mat.size(), n = mat[0].size(), start = 0;
vector<vector<int>> dirs{{0, 0}, {-1, 0}, {0, 1}, {1, 0}, {0, -1}};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
start |= mat[i][j] << (i * n + j);
}
}
queue<int> q{{start}};
unordered_set<int> visited{{start}};
while (!q.empty()) {
for (int t = q.size(); t > 0; --t) {
int cur = q.front(); q.pop();
if (cur == 0) return res;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int next = cur;
for (auto dir : dirs) {
int x = i + dir[0], y = j + dir[1];
if (x < 0 || x >= m || y < 0 || y >= n) continue;
next ^= 1 << (x * n + y);
}
if (!visited.count(next)) {
visited.insert(next);
q.push(next);
}
}
}
}
++res;
}
return -1;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1284

Minimum Operations to Remove Adjacent Ones in Matrix

Remove All Ones With Row and Column Flips

Remove All Ones With Row and Column Flips II

https://leetcode.com/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix/

LeetCode All in One 题目讲解汇总(持续更新中…)

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation