Problem: 934. 最短的桥

• 思路
• 复杂度
• Code

思路

先找到第一个岛屿，根据每一个岛屿的岛屿块的位置
多源查找这个块与第二个岛屿的距离，先找到的就是最少的距离
同时，将已遍历过的岛屿标记为-1，避免重复入队

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n^2)$

空间复杂度:

添加空间复杂度, 示例： $O(n^2)$

Code

class Solution {
    public int shortestBridge(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dir = new int[][]{{-1,0}, {1, 0}, {0, -1}, {0, 1}};
        List<int[]> firstIsland = new ArrayList<>();
        Queue<int[]> queue = new LinkedList<>();
        // 找到第一个岛屿
        // -1 标记已经遍历过
        loop:for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j] == 1){
                    queue.offer(new int[]{i, j});
                    grid[i][j] = -1;
                    break loop;
                }
            }
        }
        while(!queue.isEmpty()){
            int[] point = queue.poll();
            firstIsland.add(point);
            for (int i = 0; i < 4; i++) {
                int x = point[0] + dir[i][0];
                int y = point[1] + dir[i][1];
                if(x>=0&& x<m && y>=0 && y<n && grid[x][y] == 1){
                    queue.offer(new int[]{x, y});
                    grid[x][y] = -1;
                }
            }
        }
        // 把找到的岛屿块入队
        for(int[] island : firstIsland){
            queue.offer(island);
        }
        // 查找第二个岛屿
        int step = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] point = queue.poll();
                for (int k = 0; k < 4; k++) {
                    int x = point[0] + dir[k][0];
                    int y = point[1] + dir[k][1];
                    if(x>=0&& x<m && y>=0 && y<n){
                        if(grid[x][y] == 0) {
                            queue.offer(new int[]{x, y});
                            grid[x][y] = -1;
                        }else if (grid[x][y] == 1){
                            return step;
                        }
                    }
                }
            }
            step++;
        }
        return 0;
    }
}