【BFS】最短的桥

题目

934. 最短的桥

---

给你一个大小为 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 中恰有两个岛

解题

方法一：BFS

思路

首先遍历找到第一个为陆地的格子，然后 BFS 把第一座岛搜出来，然后从第一座岛再开一个 BFS 一旦搜到第二座岛的陆地就返回步数（注意：第二次搜索时要保证不能向内搜，所以在第一次搜索时要记录已访问的格子第二次直接跳过）。

代码

class Solution {
    static final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    int[][] grid;
    int n;
    Queue<int[]> que = new LinkedList<>();
    List<int[]> lands = new ArrayList<>();

    public int shortestBridge(int[][] _grid) {
        grid = _grid;
        n = grid.length;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) return bfs1(i, j);
            }
        }
        return -1;
    }

    int bfs1(int x, int y) {
        que.offer(new int[]{x, y});
        grid[x][y] = -1;
        while (!que.isEmpty()) {
            int[] pos = que.poll();
            lands.add(pos);
            x = pos[0];
            y = pos[1];
            for (int[] dir : DIRS) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] != 1) continue;
                que.offer(new int[]{nx, ny});
                grid[nx][ny] = -1;
            }
        }
        for (int[] land : lands) que.offer(land);
        return bfs2();
    }

    int bfs2() {
        int step = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            while (size-- > 0) {
                int[] state = que.poll();
                int x = state[0], y = state[1];
                for (int[] dir : DIRS) {
                    int nx = x + dir[0], ny = y + dir[1];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == -1) continue;
                    if (grid[nx][ny] == 1) return step;
                    else {
                        que.offer(new int[]{nx, ny});
                        grid[nx][ny] = -1;
                    }
                }
            }
            ++step;
        }
        return -1;
    }
}