欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

leetcode 934. Shortest Bridge(最短桥梁)

程序员文章站 2022-06-14 21:53:17
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 o...

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

相关标签: leetcode 算法