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

1
class Solution {
2
  public int minFlips(int[][] mat) {
3
    int m = mat.length, n = mat[0].length;
4
    Set<Integer> visited = new HashSet<>();
5
    Queue<Integer> queue = new LinkedList<>();
6
    int steps = 0;
7

8
    int initialState = toBinary(mat);
9
    queue.add(initialState);
10
    visited.add(initialState);
11

12
    while (!queue.isEmpty()) {
13
      int size = queue.size();
14

15
      for (int i = 0; i < size; i++) {
16
        int state = queue.poll();
17
        if (state == 0) return steps;
18
        int mask = 1;
19

20
        for (int y = 0; y < m; y++) {
21
          for (int x = 0; x < n; x++) {
22
            int nextState = flip(state, x, y, n, m);
23
            if (!visited.contains(nextState)) {
24
              visited.add(nextState);
25
              queue.add(nextState);
26
            }
27
            mask = mask << 1;
28
          }
29
        }
30
      }
31
      steps++;
32
    }
33
    return -1;
34
  }
35

36
  private int toBinary(int[][] M) {
37
    int bin = 0;
38
    for (int y = 0; y < M.length; y++) {
39
      for (int x = 0; x < M[0].length; x++) {
40
        bin = (bin << 1) + M[y][x];
41
      }
42
    }
43
    return bin;
44
  }
45

46
  private int flip(int state, int x, int y, int n, int m) {
47
    int flip = 1 << ((y * n) + x);
48
    flip += (x > 0) ? 1 << ((y * n) + (x - 1)) : 0;
49
    flip += (x < n - 1) ? 1 << ((y * n) + (x + 1)) : 0;
50
    flip += (y > 0) ? 1 << (((y - 1) * n) + x) : 0;
51
    flip += (y < m - 1) ? 1 << (((y + 1) * n) + x) : 0;
52
    return state ^ flip;
53
  }
54
}