网格图--Day03--网格图DFS--2658. 网格图中鱼的最大数目，1034. 边界着色，1020. 飞地的数量

思路：

题意转换：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;}
}

思路：

题目非常啰嗦且复杂，感觉在做阅读题…………

题意:给指定陆地描边

• 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上染色的格子，染回去gridfor (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;}
}

思路：

题意：求内陆。

陆地中，必须至少有一个格子要碰到边界，否则这个陆地就是所求陆地（内陆）。

• 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) {// 越界了，证明递归进来之前，是在边界上的。trueif (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);// 如果还是没碰到边界，是所求的岛屿，累加到resif (!connect) {res += area;}}}}return res;}
}