网格图–Day03–网格图DFS–2658. 网格图中鱼的最大数目，1034. 边界着色，1020. 飞地的数量
今天要训练的题目类型是：【网格图DFS】，题单来自@灵艾山茶府。
适用于需要计算连通块个数、大小的题目。
部分题目做法不止一种，也可以用 BFS 或并查集解决。
DFS函数中的三步曲：判断，处理，继续DFS。
- 判断：是否越界，是否是需要DFS的格子
- 处理：根据题意处理格子
- 继续DFS：DFS四个方向，有时候可能需要收集返回值。
2658. 网格图中鱼的最大数目
思路：
题意转换：0是水，val是陆地宝藏的数值，找到有最大数值宝藏的陆地。
是不是理解起来就简单多了？
遍历每一块陆地，对比它的价值。找到最大价值。
class Solution {
// 题意转换：0是水，val是陆地宝藏的数值，找到有最大数值宝藏的陆地。
private final int[][] DIRS = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
private int dfs(int[][] grid, int i, int j) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0) {
return 0;
}
int val = grid[i][j];
// 标记为已访问
grid[i][j] = 0;
// 用foreach写，看起来更简洁了
for (int[] d : DIRS) {
val += dfs(grid, i + d[0], j + d[1]);
}
return val;
}
public int findMaxFish(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] != 0) {
int val = dfs(grid, i, j);
res = Math.max(res, val);
}
}
}
return res;
}
}
1034. 边界着色
思路：
题目非常啰嗦且复杂，感觉在做阅读题…………
题意:给指定陆地描边
- DFS染色的时候，先染在temp矩阵上，dfs完之后再转移回去到grid，不然会影响遍历。复杂很多。
- 题目说的边界要求：
- 情况一：上下左右，只要有跟自己的color不同的，就算边界。染色！
- 情况二：当前格子在边界上，就算边界。染色！
- DFS下一个节点：要和本节点颜色相同，且没访问过的节点，才能进去。
- 最后DFS完了，将temp上染色的格子，染回去grid
class Solution {
// 题意:给指定陆地描边
private final int[][] DIRS = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
// 染色，先染在temp上，dfs完之后再转移回去到grid，不然会影响遍历。复杂很多。
private void dfs(int[][] grid, int i, int j, int color, boolean[][] visited, int[][] temp) {
// 标记已访问
visited[i][j] = true;
// 情况一：上下左右，只要有跟自己的color不同的，就算边界。染色！
int cur = grid[i][j];
if (i - 1 >= 0 && grid[i - 1][j] != cur
|| i + 1 < grid.length && grid[i + 1][j] != cur
|| j - 1 >= 0 && grid[i][j - 1] != cur
|| j + 1 < grid[0].length && grid[i][j + 1] != cur) {
temp[i][j] = color;
}
// 情况二：格子在边界上，就算边界。染色！
if (i == 0 || j == 0 || i == grid.length - 1 || j == grid[0].length - 1) {
temp[i][j] = color;
}
for (int k = 0; k < DIRS.length; k++) {
int x = i + DIRS[k][0];
int y = j + DIRS[k][1];
// xy越界
if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) {
continue;
}
// 下一个没访问过的节点，且这个节点要和当前节点是同色的
if (!visited[x][y] && grid[x][y] == cur) {
dfs(grid, x, y, color, visited, temp);
}
}
}
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
int n = grid.length;
int m = grid[0].length;
boolean[][] visited = new boolean[n][m];
int[][] temp = new int[n][m];
dfs(grid, row, col, color, visited, temp);
// dfs完了之后，将temp上染色的格子，染回去grid
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (temp[i][j] != 0) {
grid[i][j] = temp[i][j];
}
}
}
return grid;
}
}
思路：
不用temp数组的版本。
关键在于：要先判断节点是否被visited过，再判断上下左右是否不同颜色。
这个顺序不能换。因为如果visited过了，颜色可能已经被改了，判断就会有误。
这个顺序是可以不用temp的原因。
public class Solution {
// 题意:给指定陆地描边
private final int[][] DIRS = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
int m = grid.length;
int n = grid[0].length;
boolean[][] visited = new boolean[m][n];
dfs(grid, row, col, grid[row][col], color, visited);
return grid;
}
private int dfs(int[][] grid, int i, int j, int curColor, int paintColor,
boolean[][] visited) {
// 情况一：越界，说明上一个格子是边界
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {
return 1;
}
// 已访问过的单元格
if (visited[i][j]) {
return 0;
}
// 这个顺序不能换，要先判断visited，再判断颜色相同。因为如果visited过了，颜色可能已经被改了，判断就会有误。
// 情况二：遇到不同颜色的单元格，说明当前单元格是边界
if (grid[i][j] != curColor) {
return 1;
}
// 标记为已访问
visited[i][j] = true;
// 检查四个方向
int isBorder = 0;
for (int[] d : DIRS) {
isBorder += dfs(grid, i + d[0], j + d[1], curColor, paintColor, visited);
}
// 如果任何一个方向返回1，说明当前单元格是边界，需要着色
// 最后才着色
if (isBorder > 0) {
grid[i][j] = paintColor;
}
return 0;
}
}
1020. 飞地的数量
思路：
题意：求内陆。
陆地中，必须至少有一个格子要碰到边界，否则这个陆地就是所求陆地（内陆）。
- DFS搜索图中的每一个岛屿，累加返回每个岛屿的面积。
- 判断岛屿是否接触边界，如果没有接触边界（内陆），就是所求陆地，累加它的面积到res中。
class Solution {
// 题意：陆地中，必须至少有一个格子要碰到边界，否则这个陆地就是所求陆地（内陆）。
private final int[][] DIRS = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };
private boolean connect = false;
private int dfs(int[][] grid, int i, int j) {
// 越界了，证明递归进来之前，是在边界上的。true
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {
connect = true;
return 0;
}
// 0不一定是边界，这俩条件不能合在一起
if (grid[i][j] == 0) {
return 0;
}
// 标记已访问
grid[i][j] = 0;
// DFS累加，求这个岛的面积
int area = 1;
for (int k = 0; k < DIRS.length; k++) {
int x = i + DIRS[k][0];
int y = j + DIRS[k][1];
area += dfs(grid, x, y);
}
return area;
}
public int numEnclaves(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 在这里进去每次都是一个独立的岛屿，要把connect重置
if (grid[i][j] == 1) {
connect = false;
int area = dfs(grid, i, j);
// 如果还是没碰到边界，是所求的岛屿，累加到res
if (!connect) {
res += area;
}
}
}
}
return res;
}
}