Comment on page

# 1284.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;
}
HashSet<String> visited = new HashSet<String>();
queue.offer(boardToString(mat));
int step = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
return step;
}
List<String> neighbors = getAllNeighbor(head, n, m);
for (String neighbor: neighbors) {
if (!visited.contains(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++) {
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);
}
}
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);
}
}
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);
}
}