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
class Solution {
public void DFS(int[][] A, boolean[][] visited, Queue<int[]> q, int i, int j, int[][] dirs) {
if (i < 0 || j < 0 || i >= A.length || j >= A[0].length || visited[i][j] || A[i][j] == 0)
return;
visited[i][j] = true;
q.add(new int[] { i, j });
for (int[] dir : dirs)
DFS(A, visited, q, i + dir[0], j + dir[1], dirs);
}
public int shortestBridge(int[][] A) {
int m = A.length, n = A[0].length;
boolean[][] visited = new boolean[m][n];
int[][] dirs = new int[][] { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
Queue<int[]> q = new LinkedList<>();
boolean found = false;
// 1. DFS to find an island, mark it in `visited`
// Marking only one island
for (int i = 0; i < m; i++) {
if (found)
break;
for (int j = 0; j < n; j++) {
if (A[i][j] == 1) {
DFS(A, visited, q, i, j, dirs);
found = true;
break;
}
}
}
// 2. BFS to expand this island
// BFS from every point of marked island
int step = 0;
while (!q.isEmpty()) {
int size = q.size();
while (size-- > 0) {
int[] cur = q.poll();
for (int[] dir : dirs) {
int i = cur[0] + dir[0];
int j = cur[1] + dir[1];
if (i >= 0 && j >= 0 && i < m && j < n && !visited[i][j]) {
if (A[i][j] == 1)
return step;
q.add(new int[] { i, j });
visited[i][j] = true;
}
}
}
step++;
}
return -1;
}
}