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 <= 100A[i][j] == 0orA[i][j] == 1
在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）
现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。
返回必须翻转的 0 的最小数目。（可以保证答案至少是 1。）
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-bridge
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
最短的桥。
题目问的是最少需要翻转多少个0使得两个岛相连，其实就是在找两个岛之间的最短距离，所以思路是BFS。
这道题没有什么奇怪的case，首先需要解决的问题是需要把两个岛屿分清楚。我们先用DFS找到第一个岛，找的时候，我们用一个额外的visited数组记录坐标是否访问过，同时将访问过的坐标加入queue中，以便之后的BFS。只要第一个DFS递归遍历一结束，我们就可以提前结束当前的for循环，因为我们已经找到了第一个岛。此时我们用BFS的方式开始弹出之前存储的坐标，并且也以BFS的方式加入他所有没有被访问过的邻居坐标，我们判断的是如果他没有被访问过但是他的坐标值是1，那说明是一个来自第二个岛的坐标。此时就可以返回距离了。
时间O(mn)
空间O(mn)
Java实现
1 class Solution { 2 public int shortestBridge(int[][] grid) { 3 int m = grid.length; 4 int n = grid[0].length; 5 int[][] visited = new int[m][n]; 6 boolean found = false; 7 int[][] dirs = new int[][] { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }; 8 Queue<int[]> queue = new LinkedList<>(); 9 for (int i = 0; i < m; i++) { 10 if (found) { 11 break; 12 } 13 for (int j = 0; j < n; j++) { 14 if (grid[i][j] == 1) { 15 // find the first island 16 dfs(grid, visited, i, j, queue); 17 found = true; 18 break; 19 } 20 } 21 } 22 23 int steps = 0; 24 while (!queue.isEmpty()) { 25 int size = queue.size(); 26 for (int i = 0; i < size; i++) { 27 int[] cur = queue.poll(); 28 for (int[] dir : dirs) { 29 int x = cur[0] + dir[0]; 30 int y = cur[1] + dir[1]; 31 if (x >= 0 && y >= 0 && x < m && y < n && visited[x][y] == 0) { 32 if (grid[x][y] == 1) { 33 return steps; 34 } 35 queue.offer(new int[] { x, y }); 36 visited[x][y] = 1; 37 } 38 } 39 } 40 steps++; 41 } 42 return -1; 43 } 44 45 private void dfs(int[][] grid, int[][] visited, int i, int j, Queue<int[]> queue) { 46 if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0 || visited[i][j] == 1) { 47 return; 48 } 49 visited[i][j] = 1; 50 queue.offer(new int[] { i, j }); 51 dfs(grid, visited, i - 1, j, queue); 52 dfs(grid, visited, i + 1, j, queue); 53 dfs(grid, visited, i, j - 1, queue); 54 dfs(grid, visited, i, j + 1, queue); 55 } 56 }