题目链接

LeetCode

题目描述

在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）

现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。

返回必须翻转的 0 的最小数目。（可以保证答案至少是 1 。）

示例 1：

输入： A = [[0,1],[1,0]]
输出： 1

示例 2：

输入： A = [[0,1,0],[0,0,0],[0,0,1]]
输出： 2

示例 3：

输入： 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]]
输出： 1

提示：

• 2 <= A.length == A[0].length <= 100
• A[i][j] == 0 或 A[i][j] == 1

  方法一：DFS+BFS

  先找到其中一个岛屿中的一个点，然后进行DFS，把遍历到的所有点都变成2，并且加入队列
  然后使用该队列进行BFS，同时把遍历到的点0变成2，并且记录遍历的步数，然后当有一个碰到1时，返回步数（桥长度） ```java class Solution { private int[] directX, directY; Queue q; public int shortestBridge(int[][] grid) {

    directX = new int[]{-1, 0, 1, 0};
    directY = new int[]{0, 1, 0, -1};
    q = new LinkedList<>(); 
    // 利用 dfs 将第一个小岛所有值变为 2，并将小岛所有元素加入队列
    for(int i = 0; i < grid.length; ++i){
        boolean flag = false;
        for(int j = 0; j < grid[0].length; ++j){
            if(grid[i][j] == 1){
                dfs(grid, i, j);
                flag = true;
                break;
            }
        }
        if(flag){
            break;
        }
    }
    // 第一个小岛外围0变成1的层数
    int res = 0;
    while(!q.isEmpty()){
        // 一层一层的向另一个岛靠近
        int size = q.size();
        for(int i = 0; i < size; ++i){
            int[] pos = q.poll();
            // 向上下左右遍历
            for(int k = 0; k < 4; ++k){
                int x = pos[0] + directX[k];
                int y = pos[1] + directY[k];
                if(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length){
                    // 如果是 0，变成陆地，并加入队列
                    if(grid[x][y] == 0){
                        grid[x][y] = 2;
                        q.offer(new int[]{x, y});
                    // 如果是 1 说明接触到第二个小岛，返回结果
                    }else if(grid[x][y] == 1){
                        return res;
                    }
                }
            }
        }
        // 当前一层未接触到第二个小岛，层数加一
        ++res;
    }
    return res;
  

  } private void dfs(int[][] grid, int i, int j){

    if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1){
        return;
    }
    q.offer(new int[]{i, j});
    grid[i][j] = 2;
    for(int k = 0; k < 4; ++k){
        int x = i + directX[k];
        int y = j + directY[k];
        dfs(grid, x, y);
    }
  

  }

} class Node{ int r; int c; int depth; Node(int r, int c, int depth){ this.r = r; this.c = c; this.depth = depth; } } ```

• 时间复杂度 O(nm)
• 空间复杂度 O(nm)