Minimum Number of Flips to Convert Binary Matrix to Zero Matrix LeetCode solution in C++

1
class Solution {
2
 public:
3
  int dir[5] = {-1, 0, 1, 0, -1};
4

5
  int minFlips(vector<vector<int>> &mat) {
6
    int n = mat.size(), m = mat[0].size(), mask = 0;
7
    unordered_set<int> vis;
8
    queue<int> q;
9
    for (int i = 0; i < n; i++)
10
      for (int j = 0; j < m; j++) mask |= (mat[i][j] << (i * m + j));
11

12
    q.push(mask);
13
    vis.insert(mask);
14
    int step = 0;
15
    while (!q.empty()) {
16
      int sz = q.size();
17
      while (sz--) {
18
        int cur = q.front();
19
        q.pop();
20
        if (cur == 0) return step;
21

22
        for (int i = 0; i < n; i++) {
23
          for (int j = 0; j < m; j++) {
24
            int temp = cur;
25
            temp ^= (1 << (i * m + j));
26
            for (int k = 0; k < 4; k++) {
27
              int ni = i + dir[k];
28
              int nj = j + dir[k + 1];
29
              if (min(ni, nj) >= 0 && ni < n && nj < m) {
30
                temp ^= (1 << (ni * m + nj));
31
              }
32
            }
33
            if (vis.find(temp) == vis.end()) {
34
              vis.insert(temp);
35
              q.push(temp);
36
            }
37
          }
38
        }
39
      }
40
      step++;
41
    }
42
    return -1;
43
  }
44
};