695. 岛屿的最大面积

题目描述

给定一个包含了0、1的非空二维数组grid，一个岛屿是由四个方向(垂直或水平)的1构成的组合。找到给定二维数组中的最大岛屿面积。(如果没有则返回0)

示例

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

# 上面给定矩阵应返回6。不应该是11，岛屿只能包含垂直、水平方向的1。

解题思路

遍历每个格点，向4个方向探索，每访问过后将其至0表示已访问过。(一次遍历过后，不需要恢复现场)

1. 深度优先遍历

class Solution {
private:
        vector<pair<int, int>> deltas = {
            pair<int, int>(1, 0),
            pair<int, int>(-1, 0),
            pair<int, int>(0, 1),
            pair<int, int>(-1, 0)
        };
public:
    int dfs(int cur_i, int cur_j, int m, int n, vector<vector<int>>& grid){
        if(cur_i<0 || cur_j<0 || cur_i>=m || cur_j>=n || grid[cur_i][cur_j]==0)
            return 0;

        int ret = 1;
        grid[cur_i][cur_j] = 0;
        for(auto delta:deltas){
            ret += dfs(cur_i+delta.first, cur_j+delta.second, m, n, grid);
        }
        
        return ret;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        if(grid.size()==0 || grid[0].size()==0)
            return 0;
        
        int m = grid.size();
        int n = grid.size();

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

        return res;
    }
};

2. 使用stack实现的深度优先遍历

int MaxAreaOfIsland(vector<vector<int>>& grid){
    if(grid.size()==0 || grid[0].size()==0)
        return 0;

    int m = grid.size();
    int n = grid[0].size();
    int deltai[] = {1, 0, -1, 0};
    int deltaj[] = {0, 1, 0, -1};

    int ans = 0;
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            int cur = 0;
            stack<int> stacki;
            stack<int> stackj;
            
            stacki.push(i);
            stackj.push(j);
            while(!stacki.empty()){
                int cur_i = stacki.top();
                int cur_j = stackj.top();
                stacki.pop();
                stackj.pop();

                if(cur_i<0 || cur_i>=m || cur_j<0 || cur_j>=n || grid[cur_i][cur_j]==0)
                    continue;

                cur++;
                grid[cur_i][cur_j] = 0;
                for(int idx=0; idx<4; idx++){
                    stacki.push(cur_i+deltai[idx]);
                    stackj.push(cur_j+deltaj[idx]);
                }
            }

            ans = max(ans, cur);
        }
    }

    return ans;
}

3. 广度优先遍历

int MaxAreaOfIsland(vector<vector<int>>& grid){
    if(grid.size()==0 || grid[0].size()==0)
        return 0;

    int m = grid.size();
    int n = grid[0].size();
    int deltai[] = {1, 0, -1, 0};
    int deltaj[] = {0, 1, 0, -1};

    int ans = 0;
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            int cur = 0;
            queue<int> queuei;
            queue<int> queuej;
            
            queuei.push(i);
            queuej.push(j);
            while(!queuei.empty()){
                int cur_i = queuei.front();
                int cur_j = queuej.front();
                queuei.pop();
                queuej.pop();

                if(cur_i<0 || cur_i>=m || cur_j<0 || cur_j>=n || grid[cur_i][cur_j]==0)
                    continue;

                cur++;
                grid[cur_i][cur_j] = 0;
                for(int idx=0; idx<4; idx++){
                    queuei.push(cur_i+deltai[idx]);
                    queuej.push(cur_j+deltaj[idx]);
                }
            }

            ans = max(ans, cur);
        }
    }

    return ans;
}