1. 介紹

深度優先搜索（Depth-First Search，DFS）是一種用于遍歷或搜索樹或圖的算法。這種算法通過盡可能深地搜索圖的分支來探索解決方案空間，直到達到一個沒有分支的點，然后回溯

1.1 原理

1. 選擇起始點：從圖中的某個頂點開始
2. 探索分支：沿著一條路徑盡可能深地探索，直到到達一個沒有未探索鄰接點的頂點
3. 回溯：當無法進一步深入時，回溯到上一個頂點，探索其他未探索的分支
4. 重復：重復上述過程，直到所有頂點都被訪問過

比如下圖是一顆簡單的樹：

首先我們從1開始，沿著最左邊的路徑探索，于是首先找到了2這個節點，然后再深入，找到了3，3后面沒有節點了，于是回溯到2，再向右找到了4，4后面沒有節點，再回溯到2，2的節點都已探索結束，于是返回1，由1開始繼續向右探索，找到了6，然后從6開始找到了7，7后面沒有節點，回溯到6，6后面也沒有節點，回溯到1，1也沒有其他節點，于是探索結束。所以這顆樹的深度優先搜索結果就為123467.

2. 題目

3. 思路和題解

這道題其實就可以用DFS來求解，當我們對這個二維數組進行遍歷時，對于每一塊土地，就是通過上面所描述的原理，去盡可能深的尋找前后左右有土地的地方，如果沒有土地了，則進行回溯，以此類推，直到尋找結束。
當我們在尋找的時候，如果這塊土地已經找過了，為了避免重復計算，我們將其置為0，然后最后取所有島嶼的最大值即可。
代碼如下：

class Solution {public int maxAreaOfIsland(int[][] grid) {if (grid == null || grid.length == 0) {return 0;}int nr = grid.length;int nc = grid[0].length;int ans = 0 ;for(int r = 0; r < nr;r++){for(int c = 0;c < nc;c++){if(grid[r][c] == 1){ans = Math.max(ans,dfs(grid,r,c));}}}return ans;}public int dfs(int[][] grid,int r,int c){int nr = grid.length;int nc = grid[0].length;int ans = 0;if(r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == 0){return 0;}grid[r][c] = 0;ans++;ans = ans +dfs(grid,r-1,c);ans = ans +dfs(grid,r+1,c);ans = ans +dfs(grid,r,c-1);ans = ans +dfs(grid,r,c+1);return ans;}
}