网格图-Day09-网格图BFS-542.-01-矩阵,1765.-地图中的最高点,994.-腐烂的橘子
目录
网格图–Day09–网格图BFS–542. 01 矩阵，1765. 地图中的最高点，994. 腐烂的橘子
网格图–Day09–网格图BFS–542. 01 矩阵，1765. 地图中的最高点，994. 腐烂的橘子
今天要训练的题目类型是：【网格图BFS】，题单来自@ 。
适用于需要计算最短距离（最短路）的题目。
BFS的时候，最需要注意的三个点：
- step/层数什么时候加一？进去就加，还是出来再加？
- 处理节点的时候，是处理cur？还是处理cur的周边节点？
- 特别要注意：先标记，再入队！不然会超时！
今天的题目特点：
都是先找到第一层，标记，然后一层一层BFS就行了，同一个套路。
今天复杂的地方在于：找到可用的染色标记，一般0或者1原意都会是水陆，意义被占用。要么就是先标记成-1意为未访问。要么就直接使用visited数组。推荐使用visited数组，这样不容易出错。
思路：
- 先找到第一层靠近水的1
- for循环寻找所有1
- 把所有的1标记成-1，意为“未访问”
- 如果这个1靠近水（4个方向有一个为0），就染色为1，并入队。
- for循环寻找所有1
- 开始一层一层遍历（染色标记从2开始）
- 遍历cur周边的四个方向
- 索引合法，且未访问过。就先染色（标记），再进队。
- 遍历cur周边的四个方向
class Solution {
private static final int[][] DIRS = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
public int[][] updateMatrix(int[][] mat) {
int n = mat.length;
int m = mat[0].length;
Deque<int[]> que = new ArrayDeque<>();
// 先找到第一层靠近水的1
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mat[i][j] == 1) {
// 把所有的1标记成-1，意为“未访问”
mat[i][j] = -1;
boolean nearWater = false;
for (int[] d : DIRS) {
int x = i + d[0];
int y = j + d[1];
if (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == 0) {
nearWater = true;
break;
}
}
if (nearWater) {
// 先染色（标记），再进队
mat[i][j] = 1;
que.offer(new int[] { i, j });
}
}
}
}
// 开始一层一层遍历
// 染色标记从2开始
int step = 2;
while (!que.isEmpty()) {
int size = que.size();
while (size-- > 0) {
int[] cur = que.poll();
int i = cur[0];
int j = cur[1];
for (int[] d : DIRS) {
int x = cur[0] + d[0];
int y = cur[1] + d[1];
// 索引合法，且未访问过
if (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == -1) {
// 先染色（标记），再进队
mat[x][y] = step;
que.offer(new int[] { x, y });
}
}
}
step++;
}
return mat;
}
}思路：
题目提示说，和542题是一样的，搞得我兴高采烈的复制代码过去，发现是过不了的。其实两题是有区别的，但是总体思路是一样的——找到第一层，标记。然后一层一层BFS。
不同点在于：
- 第一次遍历全矩阵的时候
- 找到海水就入队，并标记高度为0
- 找到陆地，就标记为-1，未访问
- 开始一层一层遍历（染色标记从1开始）
- 遍历cur周边的四个方向
- 索引合法，且未访问过。就先染色（标记），再进队。
- 遍历cur周边的四个方向
class Solution {
private static final int[][] DIRS = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
public int[][] highestPeak(int[][] isWater) {
int[][] mat = isWater;
int n = mat.length;
int m = mat[0].length;
Deque<int[]> que = new ArrayDeque<>();
boolean[][] visited = new boolean[n][m];
// 先找到第0层
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mat[i][j] == 1) {
// 海水（1）的高度为0
// 先标记，再入队
mat[i][j] = 0;
que.offer(new int[] { i, j });
} else {
// 0的定义已经被占用，未访问的陆地，标记为-1
mat[i][j] = -1;
}
}
}
// 开始一层一层遍历
// 染色标记从1开始
int step = 1;
while (!que.isEmpty()) {
int size = que.size();
while (size-- > 0) {
int[] cur = que.poll();
for (int[] d : DIRS) {
int x = cur[0] + d[0];
int y = cur[1] + d[1];
// 索引合法，且未访问过
if (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == -1) {
// 先标记，再入队
mat[x][y] = step;
que.offer(new int[] { x, y });
}
}
}
step++;
}
return mat;
}
}思路：
这道题目是HOT100里面的。用心做。
统计BFS次数，如果BFS之后，如果还有1，那么就是-1.
- 收集0分钟时候的烂橘子，第一层
- 开始BFS
- 这一层要遍历的节点为队列中的前size个（因为后面可能会加新节点到que）
- 出队一个，cur是烂橘子，污染它周边的4个
- 当索引合法，且是好橘子。污染它，并入队，下一层再处理
- 遍历完这一层，判断que.size()是否大于0，如果还有下一层，还需要多1分钟污染，此时minute++
- BFS完了以后，检查是否还有好橘子，有则返回-1.无则返回minute
class Solution {
// 统计BFS次数，如果BFS之后，如果还有1，那么就是-1.
private static final int[][] DIRS = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
public int orangesRotting(int[][] grid) {
int res = 0;
Queue<int[]> que = new ArrayDeque<>();
int n = grid.length;
int m = grid[0].length;
// 收集0分钟时候的烂橘子，第一层
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 2) {
que.offer(new int[] { i, j });
}
}
}
// 开始BFS
while (!que.isEmpty()) {
// 这一层要遍历的节点为队列中的前size个（因为后面可能会加新节点到que）
int size = que.size();
while (size-- > 0) {
// cur是烂橘子，污染它周边的4个
int[] cur = que.poll();
for (int k = 0; k < DIRS.length; k++) {
int x = cur[0] + DIRS[k][0];
int y = cur[1] + DIRS[k][1];
// 索引合法，且是好橘子
if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1) {
// 污染它，并入队，下一层处理
grid[x][y] = 2;
que.offer(new int[] { x, y });
}
}
}
// 如果还有下一层，还需要多1分钟污染
if (que.size() > 0) {
res++;
}
}
// 检查有无没污染的橘子，有的话返回-1
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1) {
return -1;
}
}
}
return res;
}
}