网格图–Day04–网格图DFS–2684. 矩阵中移动的最大次数，1254. 统计封闭岛屿的数目，130. 被围绕的区域
今天要训练的题目类型是：【网格图DFS】，题单来自@灵茶山艾府。
适用于需要计算连通块个数、大小的题目。
部分题目做法不止一种，也可以用 BFS 或并查集解决。
2684. 矩阵中移动的最大次数
方法：DFS
思路：
class Solution {
private int res;
private void dfs(int[][] grid, int i, int j) {
res = Math.max(res, j);
// 已经到头了
if (res == grid[0].length - 1) {
return;
}
for (int k = i - 1; k <= i + 1; k++) {
if (k >= 0 && k < grid.length && grid[k][j + 1] > grid[i][j]) {
dfs(grid, k, j + 1);
}
}
// 标记走过（等于记忆化）
grid[i][j] = -1;
}
public int maxMoves(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
for (int i = 0; i < grid.length; i++) {
dfs(grid, i, 0);
}
return res;
}
}
方法：动态规划
思路：
class Solution {
public int maxMoves(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
// 初始化DP数组，存储从当前位置出发的最大移动次数
int[][] f = new int[n][m];
// 从右向左遍历列
// 更新需要grid[i][j], 但是每次实际更新的是dp[i][j-1]，所以要求j>0.最右列无需管，因为没得跳
for (int j = m - 1; j > 0; j--) {
// 遍历当前列的所有行
for (int i = 0; i < n; i++) {
// 检查当前位置(i,j)能到达的左侧三个位置（i-1,j-1）、(i,j-1)、(i+1,j-1)
for (int k = i - 1; k <= i + 1; k++) {
// 边界检查：k必须在有效行范围内，且左侧位置值小于当前位置值
if (k >= 0 && k < n && grid[k][j - 1] < grid[i][j]) {
// 更新左侧位置的最大移动次数
f[k][j - 1] = Math.max(f[k][j - 1], f[i][j] + 1);
}
}
}
}
// 找出第一列的最大移动次数（所有可能的起始位置）
int res = 0;
for (int i = 0; i < n; i++) {
res = Math.max(res, f[i][0]);
}
return res;
}
}
1254. 统计封闭岛屿的数目
思路：
统计不与边界接触的岛屿
每层dfs返回一个布尔变量，一旦遇到边界，就返回false，一直向上返回。
class Solution {
// 题意：统计不与边界接触的岛屿
private final int[][] DIRS = new int[][] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
private boolean dfs(int[][] grid, int i, int j) {
boolean flag = true;
// 标记已访问
grid[i][j] = 2;
for (int k = 0; k < DIRS.length; k++) {
int x = i + DIRS[k][0];
int y = j + DIRS[k][1];
// 下一个格子越界了，就是岛屿接触到边界了，flag赋值false
if (x < 0 || x >= grid.length || y < 0 | y >= grid[0].length) {
flag = false;
continue;
}
if (grid[x][y] == 0) {
// 拼接下层的flag，全部格子都不能接触边界
// 踩坑：不能flag = flag && dfs(grid, x, y)，会造成短路，无法触发下一层dfs
flag = dfs(grid, x, y) && flag;
}
}
return flag;
}
public int closedIsland(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 0 && dfs(grid, i, j)) {
// 返回来的标志全是true
count++;
}
}
}
return count;
}
}
130. 被围绕的区域
思路：
借用上题的代码。先dfs一次判断是否接触，再dfs多一次进行修改。
因为第一次dfs的时候，不能直接改原网格，所以要增加一个布尔数组visited来辅助。
主要逻辑：如果是O，且没有被dfs过，那么dfs它。如果dfs之后发现没有接触边界——那么执行dfs2删除
class Solution {
private final int[][] DIRS = new int[][] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
// 判断岛屿是否与“边界”接触，
private boolean dfs(char[][] grid, int i, int j, boolean[][] visited) {
// 标记已走过，这是给dfs函数用的
visited[i][j] = true;
// 这个flag是用来标记，是否接触“边界”的
boolean flag = true;
for (int k = 0; k < DIRS.length; k++) {
int x = i + DIRS[k][0];
int y = j + DIRS[k][1];
// 如果接触边界，false
if (x < 0 || x >= grid.length || y < 0 | y >= grid[0].length) {
flag = false;
continue;
}
// 探索下一个没走过的O
if (grid[x][y] == 'O' && !visited[x][y]) {
// 拼接下层的flag，全部格子都不能接触边界
// 踩坑：不能flag = flag && dfs(grid, x, y)，会造成短路，无法触发下一层dfs
flag = dfs(grid, x, y, visited) && flag;
}
}
return flag;
}
// 再dfs2这个岛，这次把每个O变成X
private void dfs2(char[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 | j >= grid[0].length || grid[i][j] == 'X') {
return;
}
grid[i][j] = 'X';
for (int k = 0; k < DIRS.length; k++) {
int x = i + DIRS[k][0];
int y = j + DIRS[k][1];
dfs2(grid, x, y);
}
}
public void solve(char[][] board) {
int n = board.length;
int m = board[0].length;
boolean[][] visited = new boolean[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 如果是O，且没有被dfs过，且dfs之后发现没有接触边界——那么执行dfs2删除
if (board[i][j] == 'O' && !visited[i][j] && dfs(board, i, j, visited)) {
dfs2(board, i, j);
}
}
}
return;
}
}