從 695. 島嶼的最大面積 入手深度優先搜素DFS

一、什麼是深度優先遍歷（DFS）

以“深度”為第一關鍵詞，每次都沿路徑到不能再前進時，才退回到最近的岔路口，然後繼續按同樣的邏輯搜索。

二、題目與解答

題目： 
Leetcode 695. 島嶼的最大面積

解答思路：

首先要遍曆數組，當發現（i,j）對應為陸地時，進行如下步驟：

（1）遞歸解法

遞歸解法最重要的是首先要確定遞歸邊界。

該題有兩個遞歸邊界：

一個是矩陣尺寸限制，

 一個是碰到了水域

一般來說，深度優先搜索類型的題可以分為主函數和輔函數，

主函數用於遍歷所有的搜索位置，判斷是否可以開始搜索，如果可以即在輔函數進行搜索。

輔函數則負責深度優先搜索的遞歸調用

本題中主函數為：int maxAreaOfIsland(vector<vector<int>>& grid);

輔函數為：int LandDFS(vector<vector<int>>& grid, int i, int j);  其中i, j 代表當前坐標。

class Solution {
public:
    // 輔函數
    int LandDFS(vector<vector<int>>& grid, int i, int j)
    {
        // 在矩陣尺寸範圍內
        if((i < grid.size()) && (i >= 0) && (j < grid[0].size()) && (j >= 0)) {
            if (grid[i][j] == 0) { // 碰到水
                return 0;
            }
            else {
                grid[i][j] = 0; 
                return 1 + LandDFS(grid, i-1, j) + LandDFS(grid, i+1, j) + 
                LandDFS(grid, i, j-1) + LandDFS(grid, i, j+1);
            }
        }
        else {
            return 0;
        }
    }

    // 主函數
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                ans = max(ans, LandDFS(grid, i, j));  // 這裡LandDFS(grid, i, j)返回的是含(i,j)的島嶼的面積
            }
        }
        return ans;
    }
};

 （2）棧解法

我們也可以使用棧（stack）實現深度優先搜索，但因為棧與遞歸的調用原理相同，而遞歸相對便於實現，因此刷題時推薦使用遞歸式寫法，同時也方便進行回溯（見下節）。

不過在實際工程上，直接使用棧可能才是最好的選擇，一是因為便於理解，二是更不易出現遞歸棧滿的情況。

class Solution {
private:
    vector<int> direction {-1, 0, 1, 0, -1};  // 每相鄰兩位即為上下左右四個方向之一
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int localArea, area = 0, x, y;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]) {  // 進入島嶼
                    localArea = 1;
                    grid[i][j] = 0;  // 抹除
                    stack<pair<int, int>> IsLand;  // 存放土地的堆棧
                    IsLand.push({i, j});  // 往堆中加入當前土地（該島第一塊土地）
                    while (!IsLand.empty()) {
                        auto [r, c] = IsLand.top();  // 從堆中取出元素，並訪問
                        IsLand.pop();  // 從堆中取出元素，並訪問
                        for (int k = 0; k < 4; k++) {  // 上下左右
                            x = r + direction[k];
                            y = c + direction[k+1];
                            if ( x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                                ++localArea;
                                grid[x][y] = 0;
                                IsLand.push({x, y});  // 往堆中加入當前土地 ( (i,j)土地的領接土地節點 )
                            }
                        }
                    }
                }
                area = max(area, localArea);
            }
        }
        return area;
    }
};

參考視頻：

https://leetcode.cn/problems/max-area-of-island/solution/dao-yu-de-zui-da-mian-ji-by-leetcode-solution/