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;
}
}