多源BFS总结

1.1020. 飞地的数量

BFS标记已经搜索过的格子避免重复搜索，一定一定要在入队时候就标记搜索

如果在出队时才标记搜索，那么下一层的节点可能会把上一层的重复入队，因为上一层前面的节点出队了，后面的还没出队因此还视为未被搜索，有重复入队的风险！

1.常规单源BFS解法：5ms 48.8 MB

class Solution {
    boolean[][] canReach;  // canReach记录grid[i][j]是否能到达边界
    int[][] grid;
    int m, n;
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int numEnclaves(int[][] _grid) {
        /*
        多源BFS:
        有一个技巧，要越过边界一定要经过边界，那么我们要求中间有哪些不能到达边界的，反过来就是要求哪些能到达边界的
        再反过来只需要从边界开始DFS看看能到达哪些陆地即可，再用总的陆地数减去能到达边界的陆地数就是不能到达的陆地数
        遍历格子的方式也可以是BFS
         */
        grid = _grid;
        m = grid.length;
        n = grid[0].length;
        canReach = new boolean[m][n];
        // 搜索4条边界的陆地
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 1) bfs(i, 0);
            if (grid[i][n - 1] == 1) bfs(i, n - 1);
        }
        for (int j = 1; j < n - 1; j++) {
            if (grid[0][j] == 1) bfs(0, j);
            if (grid[m - 1][j] == 1) bfs(m - 1, j);
        }
        // 统计不能到达边界的数目
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !canReach[i][j]) res++;
            }
        }
        return res;
    }

    // dfs(i,j)搜索与之连接的陆地并标记到canReach
    private void bfs(int i, int j) {
        // grid[i][j]可以到达边界说明与之连通的已经搜索过了，结束
        if (canReach[i][j]) return;
        Queue<int[]> que = new LinkedList<>();
        canReach[i][j] = true;  // 统一入队标记搜索(速度快很多避免重复搜索)
        que.add(new int[]{i, j});
        while (!que.isEmpty()) {
            int size = que.size();
            while (size-- > 0) {
                int[] poll = que.poll();
                int x = poll[0], y = poll[1];
                // 搜索4个方向
                for (int[] dir : dirs) {
                    int newX = x + dir[0], newY = y + dir[1];
                    // 位于区域内并且是陆地就可以到达，且不能搜回头路
                    if (newX >= 0 && newX <= m - 1 && newY >= 0 && newY <= n - 1 && grid[newX][newY] == 1 && !canReach[newX][newY]) {
                        canReach[newX][newY] = true;  // 统一入队标记搜索
                        que.add(new int[]{newX, newY});
                    }
                }
            }
        }
    }
}

2.多源BFS写法：

class Solution {
    boolean[][] canReach;  // canReach记录grid[i][j]是否能到达边界

    public int numEnclaves(int[][] grid) {
        /*
        多源BFS:
        有一个技巧，要越过边界一定要经过边界，那么我们要求中间有哪些不能到达边界的，反过来就是要求哪些能到达边界的
        再反过来只需要从边界开始BFS看看能到达哪些陆地即可，再用总的陆地数减去能到达边界的陆地数就是不能到达的陆地数
        这是多个源点的BFS，我们可以把多个节点同时入队，相当于开始就进行第二层的BFS
        时间复杂度:O(N^2)  空间复杂度:O(N)
         */
        int m = grid.length, n = grid[0].length;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        Queue<int[]> que = new LinkedList<>();
        // 搜索4条边界的陆地
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 1) {
                grid[i][0] = 2; // 访问过与边缘连通的陆地标记为2
                que.add(new int[]{i, 0});
            }
            if (grid[i][n - 1] == 1) {
                grid[i][n - 1] = 2;
                que.add(new int[]{i, n - 1});
            }
        }
        for (int j = 1; j < n - 1; j++) {
            if (grid[0][j] == 1) {
                grid[0][j] = 2;
                que.add(new int[]{0, j});
            }
            if (grid[m - 1][j] == 1) {
                grid[m - 1][j] = 2;
                que.add(new int[]{m - 1, j});
            }
        }
        while (!que.isEmpty()) {
            int size = que.size();
            while (size-- > 0) {
                int[] poll = que.poll();
                int x = poll[0], y = poll[1];
                // 搜索4个方向
                for (int[] dir : dirs) {
                    int newX = x + dir[0], newY = y + dir[1];
                    // 位于区域内并且是陆地就可以到达，且不能搜回头路
                    if (newX >= 0 && newX <= m - 1 && newY >= 0 && newY <= n - 1 && grid[newX][newY] == 1) {
                        grid[newX][newY] = 2;
                        que.add(new int[]{newX, newY});
                    }
                }
            }
        }
        // 统计不能到达边界的数目
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) res++; // 为1的就是无法到达边界的陆地
            }
        }
        return res;
    }
}

3.DFS解法：4ms 48.7 MB

class Solution {
    boolean[][] canReach;  // canReach记录grid[i][j]是否能到达边界
    int[][] grid;
    int m, n;
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int numEnclaves(int[][] _grid) {
        /*
        记忆化DFS:
        有一个技巧，要越过边界一定要经过边界，那么我们要求中间有哪些不能到达边界的，反过来就是要求哪些能到达边界的
        再反过来只需要从边界开始DFS看看能到达哪些陆地即可，再用总的陆地数减去能到达边界的陆地数就是不能到达的陆地数
         */
        grid = _grid;
        m = grid.length;
        n = grid[0].length;
        canReach = new boolean[m][n];
        // 搜索4条边界的陆地
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 1) dfs(i, 0);
            if (grid[i][n - 1] == 1) dfs(i, n - 1);
        }
        for (int j = 1; j < n - 1; j++) {
            if (grid[0][j] == 1) dfs(0, j);
            if (grid[m - 1][j] == 1) dfs(m - 1, j);
        }
        // 统计不能到达边界的数目
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !canReach[i][j]) res++;
            }
        }
        return res;
    }

    // dfs(i,j)搜索与之连接的陆地并标记到canReach
    private void dfs(int i, int j) {
        // grid[i][j]可以到达边界说明与之连通的已经搜索过了，结束
        if (canReach[i][j]) return;
        // 标记与边界连通
        canReach[i][j] = true;
        // 搜索4个方向
        for (int[] dir : dirs) {
            int newI = i + dir[0], newJ = j + dir[1];
            // 位于区域内并且是陆地就可以到达
            if (newI >= 0 && newI <= m - 1 && newJ >= 0 && newJ <= n - 1 && grid[newI][newJ] == 1) {
                dfs(newI, newJ);
            }
        }
    }
}

2.1162. 地图分析

多源BFS实际就是单源BFS的第二层，在前面加上一个超级源点指向最初入队的节点，就是普通的单源BFS

参考： ʚ自在飞花ɞ | 多个源点的广搜

class Solution {
    public int maxDistance(int[][] grid) {
        /*
        多源BFS问题(相当于单源BFS从第2层开始):
        这题是最短路径问题，求某个0到达1的最短路径的最大值
        求最短路径，首先想到的就是BFS，可以枚举每个格子0求出每个海洋到达陆地的最近距离，取最大值
        这样做的时间复杂度为O(n^4)≈1e8 必定TLE
        不妨反过来，我们从陆地1出发进行多源点的BFS
        每一圈到达的海洋0都是陆地到达的该海洋的最短路径，也就是说是这个海洋到达陆地的最短路径
        那么遍历到最后一层就是陆地1到达海洋0的最短路径最大值
         */
        int m = grid.length, n = grid[0].length;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        Queue<int[]> que = new LinkedList<>();
        // 所有的陆地入队(相当于单源BFS的第二层)
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    que.add(new int[]{i, j});
                }
            }
        }
        // 全是海洋或者陆地返回-1
        if (que.size() == m * n || que.size() == 0) return -1;
        int dis = -1;
        while (!que.isEmpty()) {
            int size = que.size();
            while (size-- > 0) {
                int[] poll = que.poll();
                int x = poll[0], y = poll[1];
                for (int[] dir : dirs) {
                    int newX = x + dir[0], newY = y + dir[1];
                    // grid[newX][newY]在区域内且为没有被访问过的海洋
                    if (newX >= 0 && newX <= m - 1 && newY >= 0 && newY <= n - 1 && grid[newX][newY] == 0) {
                        grid[newX][newY] = 2; // 访问过的海洋记为2就不会重复访问
                        que.add(new int[]{newX, newY});
                    }
                }
            }
            dis++;  // 每一圈距离+1
        }
        return dis;
    }
}

在矩阵中，关于BFS入队的类型，可以为int[] 类型的[x,y]，也可以将其化为int类型后面再进行解析

3.1765. 地图中的最高点

1.常规写法：44 ms 136.9 MB

class Solution {
    public int[][] highestPeak(int[][] isWater) {
        /*
        多源BFS：
        矩阵就是4方向的无向图
        这题要求的是从某个水域1出发后的BFS的层数能达到的方案值对应的矩阵，且任意相邻的格子高度差 至多 为 1
        多源的BFS解法就是首先让可以入队的水域1全部一次入队，遇到下一个格子直接等于本格子的值+1
        遍历完之后会出现最大值，最后的矩阵就是答案
         */
        int m = isWater.length, n = isWater[0].length;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Queue<int[]> que = new LinkedList<>();
        // 这里规定为水域为0，没有访问的土地为-1
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    isWater[i][j] = 0;
                    que.add(new int[]{i, j});
                } else {
                    isWater[i][j] = -1;
                }
            }
        }
        while (!que.isEmpty()) {
            int size = que.size();
            while (size-- > 0) {
                int[] poll = que.poll();
                int x = poll[0], y = poll[1];
                for (int[] dir : dirs) {
                    int newX = x + dir[0], newY = y + dir[1];
                    // 在区域内且没有被访问过的土地才能BFS
                    if (newX >= 0 && newX <= m - 1 && newY >= 0 && newY <= n - 1 && isWater[newX][newY] == -1) {
                        isWater[newX][newY] = isWater[x][y] + 1;
                        que.add(new int[]{newX, newY});
                    }
                }
            }
        }
        return isWater;
    }
}

化为int类型后：45 ms 158.2 MB

class Solution {
    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length, n = isWater[0].length;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Queue<Integer> que = new LinkedList<>();    // 用int代替[x,y]数组
        // 这里规定为水域为0，没有访问的土地为-1
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    isWater[i][j] = 0;
                    que.add(i * n + j);
                } else {
                    isWater[i][j] = -1;
                }
            }
        }
        while (!que.isEmpty()) {
            int size = que.size();
            while (size-- > 0) {
                int poll = que.poll();
                int x = poll / n, y = poll % n; // 解析出x与y
                for (int[] dir : dirs) {
                    int newX = x + dir[0], newY = y + dir[1];
                    // 在区域内且没有被访问过的土地才能BFS
                    if (newX >= 0 && newX <= m - 1 && newY >= 0 && newY <= n - 1 && isWater[newX][newY] == -1) {
                        isWater[newX][newY] = isWater[x][y] + 1;
                        que.add(newX * n + newY);
                    }
                }
            }
        }
        return isWater;
    }
}