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

• Time: $O(mn \cdot 2^{mn})$
• Space: $O(2^{mn})$
  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 48 49 50 51 52 class Solution { public: int minFlips(vector>& mat) { const int m = mat.size(); const int n = mat[0].size(); const int hashed = hash(mat, m, n); if (hashed == 0) return 0; const vector dirs{0, 1, 0, -1, 0}; queue q{{hashed}}; unordered_set seen{hashed}; for (int step = 1; !q.empty(); ++step) { for (int sz = q.size(); sz > 0; --sz) { const int curr = q.front(); q.pop(); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { int next = curr ^ 1 << (i * n + j); // Flip four neighbors for (int k = 0; k < 4; ++k) { const int x = i + dirs[k]; const int y = j + dirs[k + 1]; if (x < 0 || x == m || y < 0 || y == n) continue; next ^= 1 << (x * n + y); } if (next == 0) return step; if (seen.count(next)) continue; q.push(next); seen.insert(next); } } } } return -1; } private: int hash(const vector>& mat, int m, int n) { int hashed = 0; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (mat[i][j]) hashed |= 1 << (i * n + j); return hashed; } }; 
  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 48 49 class Solution { public int minFlips(int[][] mat) { final int m = mat.length; final int n = mat[0].length; final int hashed = hash(mat, m, n); if (hashed == 0) return 0; final int[] dirs = {0, 1, 0, -1, 0}; Queue q = new ArrayDeque<>(Arrays.asList(hashed)); Set seen = new HashSet<>(Arrays.asList(hashed)); for (int step = 1; !q.isEmpty(); ++step) { for (int sz = q.size(); sz > 0; --sz) { final int curr = q.poll(); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { int next = curr ^ 1 << (i * n + j); // Flip four neighbors for (int k = 0; k < 4; ++k) { final int x = i + dirs[k]; final int y = j + dirs[k + 1]; if (x < 0 || x == m || y < 0 || y == n) continue; next ^= 1 << (x * n + y); } if (next == 0) return step; if (seen.contains(next)) continue; q.offer(next); seen.add(next); } } } } return -1; } private int hash(int[][] mat, int m, int n) { int hashed = 0; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (mat[i][j] == 1) hashed |= 1 << (i * n + j); return hashed; } } 
  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 class Solution: def minFlips(self, mat: List[List[int]]) -> int: m = len(mat) n = len(mat[0]) hashed = self._hash(mat, m, n) if hashed == 0: return 0 dirs = [0, 1, 0, -1, 0] step = 0 q = collections.deque([hashed]) seen = {hashed} while q: step += 1 for _ in range(len(q)): curr = q.popleft() for i in range(m): for j in range(n): next = curr ^ 1 << (i * n + j) # Flip four neighbors for k in range(4): x = i + dirs[k] y = j + dirs[k + 1] if x < 0 or x == m or y < 0 or y == n: continue next ^= 1 << (x * n + y) if next == 0: return step if next in seen: continue q.append(next) seen.add(next) return -1 def _hash(self, mat: List[List[int]], m: int, n: int) -> int: hashed = 0 for i in range(m): for j in range(n): if mat[i][j]: hashed |= 1 << (i * n + j) return hashed