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

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

题目地址

https://leetcode.com/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix/

题目描述

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.

代码

Approach #1 BFS

Time: O(2 ^ (m * n)), Space: O(2 ^ (m * n)).

class Solution {
  public int minFlips(int[][] mat) {
        if (mat == null || mat.length == 0 || mat[0].length == 0) {
      return 0;
    }
    int n = mat.length;
    int m = mat[0].length;

    if (isallzero(boardToString(mat))) {
      return 0;
    }

    Queue<String> queue = new LinkedList<String>();
    HashSet<String> visited = new HashSet<String>();
    queue.offer(boardToString(mat));
    visited.add(boardToString(mat));
    int step = 0;
    while (!queue.isEmpty()) {
      int size = queue.size();
      for (int i = 0; i < size; i++) {
        String head = queue.poll();
        if (isallzero(head)) {
          return step;
        }

        List<String> neighbors = getAllNeighbor(head, n, m);
        for (String neighbor: neighbors) {
          if (!visited.contains(neighbor)) {
            visited.add(neighbor);
            queue.offer(neighbor);
          }
        }
      }
      step++;
    }
    return -1;
  }

  private List<String> getAllNeighbor(String matstr, int n, int m) {
    List<String> list = new ArrayList<String>();
    int[][] mat = stringToBoard(matstr, n, m);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        list.add(changeboard(mat, i, j));
        changeboard(mat, i, j);
      }
    }
    return list;
  }

  private String changeboard(int[][] mat, int x, int y) {
    int[] dx = {0, 0, -1, 1};
    int[] dy = {-1, 1, 0, 0};
    int n = mat.length;
    int m = mat[0].lenght;
    mat[x][y] = (mat[x][y] == 0) ? 1 : 0;
    for (int k = 0; k < 4; k++) {
      int nx = x + dx[k];
      int ny = y + dy[k];
      if (0 <= nx && nx < n && 0 <= ny && ny < m) {
        mat[nx][ny] = (mat[nx][ny] == 0) ? 1 : 0;
      } 
    }
    return boardToString(mat);
  }

  private String boardToString(int[][] mat) {
    int n = mat.length;
    int m = mat[0].length;
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        sb.append(mat[i][j]);
      }
    }
    return sb.toString();
  }

  private int[][] stringToBoard(String matstr, int n, int m) {
    int[][] mat = new int[n][m];
    for (int i = 0; i < matstr.length(); i++) {
      mat[i / m][i % m] = matstr.charAt(i) - '0';
    }
    return mat;
  }

  private boolean isallzero(String matstr) {
    for (int i = 0; i < matstr.length(); i++) {
      if (matstr.charAt(i) != '0') {
        return false;
      }
    }
    return true;
  }
}

Approach #2 Bit-BFS

class Solution {
  private static final int[] d = {0, 0, 1, 0, -1, 0};
  public int minFlips(int[][] mat) {
    int start = 0;
    int m = mat.length;
    int n = mat[0].length;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        start |= mat[i][j] << (i * n + j);
      }
    }
    Queue<Integer> q = new LinkedList<>(Arrays.asList(start));
    Set<Integer> seen = new HashSet<>(q);
    for (int step = 0; !q.isEmpty(); step++) {
      for (int sz = q.size(); sz > 0; sz--) {
        int cur = q.poll();
        if (cur == 0)    return step;
        for (int i = 0; i < m; i++) {
          for (int j = 0; j < n; j++) {
            int next = cur;
            for (int k = 0; k < 5; k++) {
              int r = i + d[k];
              int c = j + d[k+1];
              if (r >= 0 && r < m && c >= 0 && c < n) {
                next ^= 1 << (r * n + c);
              }
            }

            if (seen.add(next)) {
              q.offer(next);
            }
          }
        }
      }
    }
    return -1;
  }
}

Approach #3 Bit-DFS

Time: O(2 ^ (m * n)), Space: O(2 ^ (m * n)).

class Solution {
  private static final int[] d = {0, 0, 1, 0, -1, 0};
  public int minFlips(int[][] mat) {
    int start = 0;
    int m = mat.length;
    int n = mat[0].length;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        start |= mat[i][j] << i * n + j;
      }
    }
    Deque<int[]> stk = new ArrayDeque<>();
    stk.push(new int[]{start, 0});
    Map<Integer, Integer> seenSteps = new HashMap<>();
    seenSteps.put(start, 0);
    while (!stk.isEmpty()) {
      int[] a = stk.pop();
      int cur = a[0];
      int step = a[1];
      for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
          int next = cur;
          for (int k = 0; k < 5; k++) {
            int r = i + d[k];
]            if (r >= 0 && r < m && c >= 0 && c < n) {
              next ^= 1 << r * n + c;
            }
          }
          if (seenSteps.getOrDefault(next, Integer.MAX_VALUE) > step + 1) {
            seenSteps.put(next, step + 1);
            stk.push(new int[]{next, step + 1});
          }
        }
      }
    }
    return seenSteps.getOrDefault(0, -1);
  }
}