Given a m x n
binary matrix mat
. In one step, you can choose one cell and flip it and all the four neighbours of it if they exist (Flip is changing 1 to 0 and 0 to 1). A pair of cells are called neighboors if they share one edge.
Return the minimum number of steps required to convert mat
to a zero matrix or -1 if you cannot.
Binary matrix is a matrix with all cells equal to 0 or 1 only.
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 don't need to change it.
Example 3:
Input: mat = [[1,1,1],[1,0,1],[0,0,0]] Output: 6
Example 4:
Input: mat = [[1,0,0],[1,0,0]] Output: -1 Explanation: Given matrix can't be a zero matrix
Constraints:
m == mat.length
n == mat[0].length
1 <= m <= 3
1 <= n <= 3
mat[i][j]
is 0 or 1.
Solution: BFS + bitmask
Time complexity: O(2^(m*n))
Space complexity: O(2^(m*n))
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
// Author: Huahua class Solution { public: int minFlips(vector<vector<int>>& mat) { const int m = mat.size(); const int n = mat[0].size(); const vector<int> dirs{0, 1, 0, -1, 0, 0}; auto flip = [&](int s, int x, int y) { for (int i = 0; i < 5; ++i) { const int tx = x + dirs[i]; const int ty = y + dirs[i + 1]; if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue; s ^= (1 << ty * n + tx); } return s; }; int steps = 0; queue<int> q; vector<int> seen(1 << (n * m)); int start = 0; for (int y = 0; y < m; ++y) for (int x = 0; x < n; ++x) start |= (mat[y][x] << (y * n + x)); q.push(start); seen[start] = 1; while (!q.empty()) { int size = q.size(); while (size--) { int s = q.front(); if (s == 0) return steps; q.pop(); for (int y = 0; y < m; ++y) for (int x = 0; x < n; ++x) { int t = flip(s, x, y); if (seen[t]) continue; seen[t] = 1; q.push(t); } } ++steps; } return -1; } }; |