<Data Structures/Algorithms> leetcode hot100 - 695.Max Area of Island

[LeetCode hot 100] 695. Max Area of Island

Problem Link

This is a commonly tested problem. It is well-suited for DFS. Starting from each point, we perform a depth-first search in all four directions. We maintain a visited array to mark whether each point has already been visited—if it has, we skip it to avoid double counting.

If we encounter a 0 or go out of bounds, we return 0. Otherwise, the area is the sum of the areas from the four directions plus 1 (for the current cell itself). If we visit an already visited cell, we also return 0, meaning either it’s a duplicate visit during the current calculation, or it has already been counted from another starting point.

Complete code:

class Solution {
public:
    int dfs(vector<vector<int>>& grid, int idx1, int idx2, vector<vector<bool>>& visited){
        if(idx1 < 0 || idx1 >= grid.size() || idx2 < 0 || idx2 >= grid[0].size()){
            return 0;
        }
        if(visited[idx1][idx2] || grid[idx1][idx2] == 0) return 0;
        visited[idx1][idx2] = true;
        return dfs(grid, idx1 - 1, idx2, visited) +
            dfs(grid, idx1 + 1, idx2, visited) +
            dfs(grid, idx1, idx2 - 1, visited) + 
            dfs(grid, idx1, idx2 + 1, visited) + 1;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        vector<vector<bool>> visited;
        for(int i = 0; i < grid.size(); i++){
            vector<bool> tmp(grid[0].size(), false);
            visited.push_back(tmp);
        }
        int maxArea = 0;
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                maxArea = max(maxArea, dfs(grid, i, j, visited));
            }
        }
        return maxArea;
    }
};

中文原文

[LeetCode hot 100] 695. 岛屿的最大面积

题目链接

我看这还是一个常考的题目。这种题适合用dfs，从每一个点向四周深度优先搜索，用一个visited数组保存每个点是否被访问过，如果访问过就不要重复计算了。如果访问到0，或者到界外了，就返回0，否则就是上下左右的面积之和再+1（自己本身还占一格）。遇到访问过的也是直接返回0，表示要么在这一次计算中重复访问了，要么就是之前在从别的点开始计算时已经计算过了。

完整代码如下：

class Solution {
public:
    int dfs(vector<vector<int>>& grid, int idx1, int idx2, vector<vector<bool>>& visited){
        if(idx1 < 0 || idx1 >= grid.size() || idx2 < 0 || idx2 >= grid[0].size()){
            return 0;
        }
        if(visited[idx1][idx2] || grid[idx1][idx2] == 0) return 0;
        // cout<<idx1<<","<<idx2<<endl;
        visited[idx1][idx2] = true;
        return dfs(grid, idx1 - 1, idx2, visited) +
            dfs(grid, idx1 + 1, idx2, visited) +
            dfs(grid, idx1, idx2 - 1, visited) + 
            dfs(grid, idx1, idx2 + 1, visited) + 1;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        vector<vector<bool>> visited;
        for(int i = 0; i < grid.size(); i++){
            vector<bool> tmp(grid[0].size(), false);
            visited.push_back(tmp);
        }
        int maxArea = 0;
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                maxArea = max(maxArea, dfs(grid, i, j, visited));
                
            }
        }
        return maxArea;
    }
};