from collections import deque
from copy import deepcopy
class Solution:
def minFlips(self, mat):
m, n = len(mat), len(mat[0])
def mat_to_int(matrix):
val = 0
for i in range(m):
for j in range(n):
if matrix[i][j]:
val |= (1 << (i * n + j))
return val
def flip(state, i, j):
for dx, dy in [(0,0),(1,0),(-1,0),(0,1),(0,-1)]:
ni, nj = i+dx, j+dy
if 0 <= ni < m and 0 <= nj < n:
state ^= (1 << (ni * n + nj))
return state
start = mat_to_int(mat)
queue = deque([(start, 0)])
visited = set([start])
while queue:
state, steps = queue.popleft()
if state == 0:
return steps
for i in range(m):
for j in range(n):
new_state = flip(state, i, j)
if new_state not in visited:
visited.add(new_state)
queue.append((new_state, steps+1))
return -1
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
class Solution {
public:
int minFlips(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
auto matToInt = [&](vector<vector<int>>& matrix) {
int val = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (matrix[i][j])
val |= (1 << (i * n + j));
return val;
};
auto flip = [&](int state, int i, int j) {
static const int dx[] = {0, 1, -1, 0, 0};
static const int dy[] = {0, 0, 0, 1, -1};
for (int k = 0; k < 5; ++k) {
int ni = i + dx[k], nj = j + dy[k];
if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
state ^= (1 << (ni * n + nj));
}
}
return state;
};
int start = matToInt(mat);
queue<pair<int, int>> q;
unordered_set<int> visited;
q.push({start, 0});
visited.insert(start);
while (!q.empty()) {
auto [state, steps] = q.front(); q.pop();
if (state == 0) return steps;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int new_state = flip(state, i, j);
if (!visited.count(new_state)) {
visited.insert(new_state);
q.push({new_state, steps + 1});
}
}
}
}
return -1;
}
};
import java.util.*;
class Solution {
public int minFlips(int[][] mat) {
int m = mat.length, n = mat[0].length;
int matToInt(int[][] matrix) {
int val = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (matrix[i][j] == 1)
val |= (1 << (i * n + j));
return val;
}
int flip(int state, int i, int j) {
int[] dx = {0, 1, -1, 0, 0};
int[] dy = {0, 0, 0, 1, -1};
for (int k = 0; k < 5; k++) {
int ni = i + dx[k], nj = j + dy[k];
if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
state ^= (1 << (ni * n + nj));
}
}
return state;
}
int start = matToInt(mat);
Queue<int[]> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.offer(new int[]{start, 0});
visited.add(start);
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int state = curr[0], steps = curr[1];
if (state == 0) return steps;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int new_state = flip(state, i, j);
if (!visited.contains(new_state)) {
visited.add(new_state);
queue.offer(new int[]{new_state, steps + 1});
}
}
}
}
return -1;
}
}
/**
* @param {number[][]} mat
* @return {number}
*/
var minFlips = function(mat) {
const m = mat.length, n = mat[0].length;
const matToInt = (matrix) => {
let val = 0;
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (matrix[i][j])
val |= (1 << (i * n + j));
return val;
};
const flip = (state, i, j) => {
const dirs = [[0,0],[1,0],[-1,0],[0,1],[0,-1]];
for (let [dx, dy] of dirs) {
const ni = i + dx, nj = j + dy;
if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
state ^= (1 << (ni * n + nj));
}
}
return state;
};
const start = matToInt(mat);
const queue = [[start, 0]];
const visited = new Set([start]);
while (queue.length) {
const [state, steps] = queue.shift();
if (state === 0) return steps;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
const new_state = flip(state, i, j);
if (!visited.has(new_state)) {
visited.add(new_state);
queue.push([new_state, steps + 1]);
}
}
}
}
return -1;
};
You are given a binary matrix mat of size m x n, where each cell contains either a 0 or a 1. In one move, you can pick any cell and "flip" it, which means toggling the value of that cell and all of its 4 direct neighbors (up, down, left, right) within the matrix. Your goal is to find the minimum number of flips needed to convert the entire matrix to a zero matrix (all cells are 0). If it is impossible, return -1.
Constraints:
-1 if not possible.At first glance, the problem seems to require trying all possible combinations of flips, as flipping one cell can affect multiple cells at once. For a small matrix, brute-forcing all possible flip sequences could work, but this quickly becomes infeasible as the size grows. We need an approach that guarantees the minimal number of flips and can efficiently avoid redundant work.
Since each flip is reversible and the order of flips doesn't matter (flipping the same cell twice is like not flipping it at all), we can think of each state of the matrix as a node in a graph, where each flip is an edge to a new state. The problem then becomes finding the shortest path from the initial state to the all-zero state. This is a classic scenario for Breadth-First Search (BFS).
To efficiently track states and avoid revisiting, we need a way to represent the matrix compactly, such as encoding it as an integer bitmask.
We'll use Breadth-First Search (BFS) to explore all possible states, starting from the initial matrix. Each time we flip a cell, we create a new state. BFS ensures that we find the minimum number of flips because it explores states in order of increasing number of moves.
-1.
This approach is both efficient and guarantees the minimum number of flips.
Let's consider a simple example: mat = [[0,1,0],[1,0,1],[0,1,0]]
For this example, the BFS will eventually reach the all-zero matrix, and the function will return the minimum number of flips required.
m x n matrix, there are 2^(m*n) possible states (each cell can be flipped or not). Brute-force would try all sequences, which is exponential and infeasible for larger matrices.
2^(m*n). For each state, we may try up to m*n possible flips. Thus, the overall time complexity is O((m*n) * 2^(m*n)). The space complexity is also O(2^(m*n)) to store visited states.
By modeling the problem as a shortest-path search in the space of matrix states, and using BFS with bitmask encoding for efficiency, we can find the minimum number of flips required to turn any small binary matrix into a zero matrix. This approach leverages the small problem size and the properties of the flip operation, ensuring both correctness and optimality.