思路：

題意轉換：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;}
}