网格图--Day04--网格图DFS--2684. 矩阵中移动的最大次数，1254. 统计封闭岛屿的数目，130. 被围绕的区域

方法：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;}
}

思路：

统计不与边界接触的岛屿

每层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赋值falseif (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)，会造成短路，无法触发下一层dfsflag = 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)) {// 返回来的标志全是truecount++;}}}return count;}
}

思路：

借用上题的代码。先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];// 如果接触边界，falseif (x < 0 || x >= grid.length || y < 0 | y >= grid[0].length) {flag = false;continue;}// 探索下一个没走过的Oif (grid[x][y] == 'O' && !visited[x][y]) {// 拼接下层的flag，全部格子都不能接触边界// 踩坑：不能flag = flag && dfs(grid, x, y)，会造成短路，无法触发下一层dfsflag = dfs(grid, x, y, visited) && flag;}}return flag;}// 再dfs2这个岛，这次把每个O变成Xprivate 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;}
}