題目網址：https://leetcode.cn/problems/max-area-of-island/

題意：給一 m x n 的矩陣 grid。

島嶼是由一些相鄰的 1 （代表土地）所構成的組合, 這里的「相鄰」要求兩個 1 必須在水平 or 垂直的四個方向上相鄰。

假設 grid 的邊界都被 0（代表水）包圍著。

返回 grid 中最大的島嶼面積。如果沒有島嶼, 則返回 0。

Solution：

想法：利用 DFS, 以每一個 grid[i][j] 作為起點做 DFS 計算 area, 一旦拜訪過, 就將 grid[i][j] 設為 0, 避免遞迴遍歷時 area 重複計算

  • 若 grid[i][j] == 1 : area++, 並遞迴遍歷四個方向
  • 若 grid[i][j] == 0 : 直接返回
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();

        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int area = 0;
                dfs(grid, i, j, area);
                res = max(res, area);
            }
        }
        return res;
    }

private:
    int m, n;
    vector<pair<int, int>> dirs = {
        {0, 1}, {0, -1},
        {1, 0}, {-1, 0}
    };

    void dfs(vector<vector<int>>& grid, const int i, const int j, int& area){
        if (outOfBound(i, j) || grid[i][j] == 0) {
            return;
        }

        // 設為已拜訪, 避免重覆計算到 area
        grid[i][j] = 0;
        ++area;

        for (const auto& [dirY, dirX] : dirs) {
            const int r = i + dirY, c = j + dirX;
            dfs(grid, r, c, area);
        }
    }

    bool outOfBound(const int i, const int j){
        if (i < 0 || i == m || j < 0 || j == n) {
            return true;
        }
        return false;
    }
};
  • time：$O(m \cdot n)$ ➔ 遍歷 grid, 且每個 cell 最多被拜訪一次
  • space：$O(m \cdot n)$ ➔ 取決於遞迴深度, worse case：整個 grid 都是 1