In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)
Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.
Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)
Example 1:
Input: A = [[0,1],[1,0]]
Output: 1
Example 2:
Input: A = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2
Example 3:
Input: A = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1
Constraints:
2 <= A.length == A[0].length <= 100
A[i][j] == 0 or A[i][j] == 1
Solution:
class Solution {
int[] dx = new int[]{-1, 0, 0, 1};
int[] dy = new int[]{0, -1, 1, 0};
public int shortestBridge(int[][] A) {
int m = A.length, n = A[0].length;
boolean markFinish = false;
for (int i = 0; i < m; i ++) {
for (int j = 0; j < n; j ++) {
if (A[i][j] == 1) {
mark(i, j, A);
markFinish = true;
break;
}
}
if (markFinish) break;
}
// for (int [] a : A) System.out.println(Arrays.toString(a));
int res = Integer.MAX_VALUE;
for (int i = 0; i < m; i ++) {
for (int j = 0; j < n; j ++) {
if (A[i][j] == 2) {
boolean[][] visited = new boolean[m][n];
res = Math.min(res, bfs(i, j, A, visited));
}
}
}
return res;
}
private int bfs(int x, int y, int[][] A, boolean[][] visited) {
int m = A.length, n = A[0].length;
Deque<int[]> queue = new ArrayDeque();
queue.offer(new int[]{x, y});
visited[x][y] = true;
int step = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i ++) {
int[] curr = queue.poll();
int currX = curr[0], currY= curr[1];
if (A[currX][currY] == 1) {
return step - 1;
}
for (int k = 0; k < 4; k ++) {
int nx = currX + dx[k];
int ny = currY + dy[k];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && A[nx][ny] != 2 && !visited[nx][ny]) {
visited[nx][ny] = true;
queue.offer(new int[]{nx, ny});
}
}
}
step ++;
}
return Integer.MAX_VALUE;
}
private void mark(int x, int y, int[][] A) {
int m = A.length, n = A[0].length;
A[x][y] = 2;
for (int k = 0; k < 4; k ++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && A[nx][ny] == 1) {
mark(nx, ny, A);
}
}
}
}