leetcode 934. Shortest Bridge（最短桥梁）

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

Constraints:
2 <= A.length == A[0].length <= 100
A[i][j] == 0 or A[i][j] == 1

有两个岛（岛指的是上下左右相连的1），问要把两个岛连在一起，至少需要把多少个0变成1

思路：
一个岛看作起点，一个岛看作终点，每个岛上有很多个1，所以是多起点多终点问题。

从一个岛上的每一个1出发，向外扩展（上下左右方向），每扩一层相当于变换一个0到1，因为相当于从外面一圈的0中选一个方向变成1。
然后从扩展的一层进一步扩展，直到扩展到另一个岛（有1的地方）就返回扩展的层数，也就是结果。这一圈一圈扩展的过程就是BFS。

那怎么区别扩展时遇到的1是起点岛还是终点岛，而且要防止重复访问呢，这就需要把起点岛和扩展到的地方的值都变成0，1以外的数字，比如2。只要遇到2就说明是起点的地盘，或者这个位置已经来过了，直接pass。

还有个问题就是既然要从第一个岛上的每一个1出发，就需要知道哪些位置是第一个岛的地盘。遍历每个位置，当发现一个1就做DFS，把相连的1（一个岛的1都是相连的）全都装入queue，方便后面做BFS。

//5ms
class Solution {
    int m = 0;
    int n = 0;
    Queue<int[]> queue = new LinkedList<>();
    public int shortestBridge(int[][] A) {
        m = A.length;
        n = A[0].length;
        boolean found = false;
        int result = 0;
        
        //把第一个island装入queue
        for(int i = 0; i < m & !found; i++) {
            for(int j = 0; j < n & !found; j++) {
                if(A[i][j] == 1) {
                    dfs(i, j, A);
                    found = true; //同时break两层
                }
            }
        }
        
        int[] offset = new int[]{-1, 0, 1, 0, -1};
        //第一个island每个点出发BFS，先找到第二个island上点的返回结果
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                int[] tmp = queue.poll();
                for(int j = 0; j < 4; j ++) {
                    int row = tmp[0] + offset[j];
                    int col = tmp[1] + offset[j+1];
                    if(row < 0 || row >= m || col < 0 || col >= n || A[row][col] == 2) continue;
                    if(A[row][col] == 1) return result;
                    A[row][col] = 2; //防止重复探索
                    queue.offer(new int[]{row, col});
                }
            }
            result ++;
        }
        return 0;
    }
    
    void dfs(int r, int c, int[][] A) {
        if(r < 0 || c < 0 || r >= m || c >= n || A[r][c] != 1) return;
        A[r][c] = 2;
        queue.offer(new int[]{r, c});
        dfs(r - 1, c, A);
        dfs(r + 1, c, A);
        dfs(r, c - 1, A);
        dfs(r, c + 1, A);
    }
}

参考资料

本文地址：https://blog.csdn.net/level_code/article/details/112253609