Leetcode第695题. Max Area of Island

原题地址如下：https://leetcode.com/problems/max-area-of-island/description/

使用深度优先搜索的方案

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), ans = 0;
        for (int i = 0; i < m; i++) 
            for (int j = 0; j < n; j++) 
                if (grid[i][j] == 1) ans = max(ans, dfs(grid, i, j));//当前结点的值为1才深度优先遍历
        return ans;
    }
private:
    int dfs(vector<vector<int>>& grid, int row, int col) {
        int m = grid.size(), n = grid[0].size(), area = 1;//一旦进入 因为当前结点的值为1 首先将其对应的area设为1
        grid[row][col] = 0;//将这个点的值设为2 因为这个点已经被处理过了 

        vector<int> dir({-1,0,1,0,-1});//这是一个巧妙的设置遍历上下左右的点的方式 减少代码书写
        for (int i = 0; i < 4; i++) {
            int r = row+dir[i], c = col+dir[i+1];//依次遍历当前处理结点的上，右，下，左四个点
            if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) //结点在范围内 且该节点的值为1 排除所有为0的点以及访问过的点 避免重复
                area += dfs(grid, r, c);
        }
        return area;
    }
};

这道题目的关键在于设置当前结点的面积area的计算方案上。在遍历四周结点的同时，需要考虑到排除重复搜索的问题：

1. 如果当前结点值为0 直接跳过。
2. 如果当前结点的值为2（任意不为1值）代表这个结点已经在之前处理过了：有可能是直接遍历过了这个点，也有可能是在求解其他的点的面积的时候遍历过了这个点。总之这些点是属于其他的联通集合，我们就不需要再对这些点进行处理。一个是减少搜索的重复，二是可以直接避免重复计算。