In a given 2D binary array
A
, there are two islands. (An island is a 4-directionally connected group of 1
s not connected to any other 1s.)
Now, we may change
0
s to 1
s so as to connect the two islands together to form 1 island.
Return the smallest number of
0
s that must be flipped. (It is guaranteed that the answer is at least 1.)
Example 1:
Input: [[0,1],[1,0]] Output: 1
Example 2:
Input: [[0,1,0],[0,0,0],[0,0,1]] Output: 2
Example 3:
Input: [[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
Note:
1 <= A.length = A[0].length <= 100
A[i][j] == 0
orA[i][j] == 1
BFS
先标记出一个岛,然后做BFS直到碰到另一个岛
注意dis的初始值是 -1
class Solution { public int shortestBridge(int[][] arr) { Queue<int[]> que = new LinkedList<>(); for (int i = 0; i < arr.length; i++) { boolean f = false; for (int j = 0; j < arr[0].length; j++) { if (arr[i][j] == 1) { dfs(arr, i, j, que); f = true; break; } } if (f) break; } int dis = -1; while (!que.isEmpty()) { for (int size = que.size(); size > 0; size--) { int[] top = que.poll(); int i = top[0], j = top[1]; if (i < 0 || j < 0 || i >= arr.length || j >= arr[0].length || arr[i][j] == 3) continue; if (arr[i][j] == 1) return dis; arr[i][j] = 3; que.add(new int[]{i + 1, j}); que.add(new int[]{i, j + 1}); que.add(new int[]{i - 1, j}); que.add(new int[]{i, j - 1}); } dis++; } return 0; } private void dfs(int[][] arr, int i, int j, Queue<int[]> que) { if (i < 0 || j < 0 || i >= arr.length || j >= arr[0].length || arr[i][j] == 0 || arr[i][j] == 2) return; arr[i][j] = 2; que.add(new int[]{i, j}); dfs(arr, i + 1, j, que); dfs(arr, i - 1, j, que); dfs(arr, i, j + 1, que); dfs(arr, i, j - 1, que); } }
No comments:
Post a Comment