LeetCode面试题 16.19. 水域大小
原题链接:水域大小

1. 难点:

如何计算每个水域的大小,并不会把水域的子集添加进去。

2. 思路

循环遍历二维数组,当碰到0时进入深度搜索,然后八个方向广度搜索,计算每个水域的大小,被记录过的0标记为1,避免重复统计。

3. 代码注释

变量定义的解释

void dfs(vector<vector<int>>& land, int x, int y,int& count)

- vector<vector<int>> &land  矩阵,因为需要修改原矩阵所以使用&  
- int x,int y  二维数组的下标land[x][y]  
- int count  用于记录水域大小,初值为0
   class Solution {
public:
    void dfs(vector<vector<int>>& land, int x, int y,
    int& count)
{    /*设置出口*/
     //超出边界
    if (x<0 || y<0 || x>land.size() - 1 || y>land.begin()->size() - 1)              
        return;     
    if (land[x][y])                 //当前位置不是0
        return;
    
    count++;
    land[x][y] = 1;                 //避免属于多个水域造成重复的现象

    dfs(land, x-1, y , count);      //八个方向搜索
    dfs(land, x+1, y , count);
    dfs(land, x,  y-1, count);
    dfs(land, x,  y+1, count);
    dfs(land, x-1,y-1, count);
    dfs(land, x-1,y+1, count);
    dfs(land, x+1,y-1, count);
    dfs(land, x+1,y+1, count);

}
vector<int> pondSizes(vector<vector<int>>& land) {
    vector<int> vec;
    /*遍历整个二维数组*/
    for (int i=0;i<land.size();i++)
    {
        for (int j=0;j<land.begin()->size();j++)
        {
            if (!land[i][j])    //为0才进入深度搜索
            {
                int count = 0;  //记录水域的大小
                dfs(land, i, j, count);
                vec.push_back(count);
            }
        }
    }
    sort(vec.begin(), vec.end());
    return vec;
}
}; 

4. 总结反思

代码的关键在于,计算过的0修改为1,这样解决了重复统计的困扰,第一个进入水域的0就可以统计整个水域的大小,之后的不会再碰到该水域,避免了重复。