695. 岛屿的最大面积

Problem: 695. 岛屿的最大面积

思路

注意：这道题目真的很诡异visted[x][y] = true;这玩意我写在dfs里面,就没有问题，写在maxAreaOfIsland就™的栈溢出。不知道什么脑瘫错误。

用dfs搜索一个岛屿的全部地块，每一个地块+1，注意初始搜搜索的时候地块为1，最后每搜索一个岛屿，比较一下得到最多地块数量。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {
public:
    vector<vector<bool>> visted;
    int ROWCNT;   // 行数
    int CLOWNCNT; // 列数
    int tempSize;
    void dfs(int x, int y, vector<vector<int>>& grid) {
        visted[x][y] = true;
        pair<int, int> neigbors[4]{
            pair<int, int>(x, y + 1), pair<int, int>(x + 1, y),
            pair<int, int>(x, y - 1), pair<int, int>(x - 1, y)};
        for (pair<int, int> neigbor : neigbors) {
            if (neigbor.first >= ROWCNT || neigbor.second >= CLOWNCNT ||
                neigbor.first < 0 || neigbor.second < 0) // 越界
                continue;
            if (grid[neigbor.first][neigbor.second] != 1) // 不是岛屿
                continue;
            if (visted[neigbor.first][neigbor.second]) // 访问过了
                continue;
            dfs(neigbor.first, neigbor.second,grid);
            visted[x][y] = true;
            tempSize+=1;
        }
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        ROWCNT = grid.size();
        CLOWNCNT = grid[0].size();
        visted = vector<vector<bool>>(ROWCNT, vector<bool>(CLOWNCNT, false));
        int maxSize = 0;
        for (int i = 0; i < ROWCNT; i++) {
            for (int j = 0; j < CLOWNCNT; j++) {
                if (grid[i][j] == 1 && !visted[i][j]) { // 陆地 没有遍历过
                    tempSize = 1;
                    // visted[x][y] = true;
                    dfs(i, j, grid);
                    maxSize = std::max(tempSize,maxSize);
                }
            }
        }
        return maxSize;
    }
};