LeetCode_BFS_中等_934.最短的桥

亦凉 2023-10-07 20:38 41阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。

岛是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中恰好存在两座岛 。

你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成一座岛 。

**返回必须翻转的 0 的最小数目。**

**示例 1：**  
输入：grid = \[\[0,1\],\[1,0\]\]  
输出：1

**示例 2：**  
输入：grid = \[\[0,1,0\],\[0,0,0\],\[0,0,1\]\]  
输出：2

**示例 3：**  
输入：grid = \[\[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

**提示：**  
n == grid.length == grid\[i\].length  
2 <= n <= 100  
grid\[i\]\[j\] 为 0 或 1  
grid 中恰有两个岛

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/shortest-bridge

## 2.思路 ##

（1）BFS  
思路参考[本题官方题解][Link 1]。

① 通过遍历找到数组 grid 中的 1 后进行广度优先搜索，此时可以得到第一座岛的位置集合，记为 island，并将其位置全部标记为 −1。  
② 从 island 中的所有位置开始进行广度优先搜索，当它们到达了任意的 1 时，即表示搜索到了第二个岛，搜索的层数就是答案。

## 3.代码实现（Java） ##

//思路1————BFS
    class Solution {
        
        public int shortestBridge(int[][] grid) {
        
            int n = grid.length;
            // dirs 记录遍历的四个方向
            int[][] dirs = {
        {
        -1, 0}, {
        1, 0}, {
        0, 1}, {
        0, -1}};
            List<int[]> island = new ArrayList<>();
            Queue<int[]> queue = new ArrayDeque<>();
            for (int i = 0; i < n; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (grid[i][j] == 1) {
        
                        queue.offer(new int[]{
        i, j});
                        grid[i][j] = -1;
                        while (!queue.isEmpty()) {
        
                            int[] land = queue.poll();
                            int x = land[0];
                            int y = land[1];
                            island.add(land);
                            for (int k = 0; k < 4; k++) {
        
                                int nextX = x + dirs[k][0];
                                int nextY = y + dirs[k][1];
                                if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < n && grid[nextX][nextY] == 1) {
        
                                    queue.offer(new int[]{
        nextX, nextY});
                                    //标记 (nextX, nextY)，表示已经访问过该点
                                    grid[nextX][nextY] = -1;
                                }
                            }
                        }
                        /*
                        	(1) 此时已经找到了题目中描述的两座岛中的一座，并且组成岛的每块陆地的坐标位置都保存在 island 中。
    						(2) 从 island 中的所有坐标位置开始进行 BFS，当它们达到了任意的 1 时，即表示搜索到了第二座岛，
    							此时搜索的层数即为答案，在下面的代码中使用 step 来记录。
    					*/
                        for (int[] land : island) {
        
                            queue.offer(land);
                        }
                        int step = 0;
                        while (!queue.isEmpty()) {
        
                            int size = queue.size();
                            for (int k = 0; k < size; k++) {
        
                                int[] land = queue.poll();
                                int x = land[0];
                                int y = land[1];
                                for (int d = 0; d < 4; d++) {
        
                                    int nextX = x + dirs[d][0];
                                    int nextY = y + dirs[d][1];
                                    if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < n) {
        
                                        if (grid[nextX][nextY] == 0) {
        
                                            queue.offer(new int[]{
        nextX, nextY});
                                            //标记 (nextX, nextY)，表示已经访问过该点
                                            grid[nextX][nextY] = -1;
                                        } else if (grid[nextX][nextY] == 1) {
        
                                            return step;
                                        }
                                    }
                                }
                            }
                            step++;
                        }
                    }
                }
            }
            return 0;
        }
    }

[Link 1]: https://leetcode.cn/problems/shortest-bridge/solution/zui-duan-de-qiao-by-leetcode-solution-qe44/