？C++刷LeetCode（面试题 16.19. 水域大小）【深度优先搜索】

糖逗

题目描述：

1. 面试题 16.19. 水域大小
   
2. 你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
   
3. 
   
4. 示例：
   
5. 
   
6. 输入：
   
7. [
   
8.   [0,2,1,0],
   
9.   [0,1,0,1],
   
10.   [1,1,0,1],
    
11.   [0,1,0,1]
    
12. ]
    
13. 输出： [1,2,4]
    
14. 提示：
    
15. 
    
16. 0 < len(land) <= 1000
    
17. 0 < len(land[i]) <= 1000

复制代码

1. class Solution {
   
2. private:
   
3.     vector<vector<int> >direct = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
   
4. public:
   
5.     void dfs(vector<vector<int> >&land, int& res1, int i, int j){
   
6.         if(i < 0 || j < 0 || i >= land.size() || j >= land[0].size() || land[i][j] != 0)return;
   
7.         res1++;
   
8.         land[i][j] = 3;
   
9.         for(auto cha : direct){
   
10.             dfs(land, res1, i + cha[0], j + cha[1]);
    
11.         }
    
12.         
    
13.     }
    
14.     vector<int> pondSizes(vector<vector<int>>& land) {
    
15.         vector<int> res;
    
16.         int len1 = land.size(), len2 = land[0].size();
    
17.         for(int i = 0; i < len1; i++){
    
18.             for(int j = 0; j < len2; j++){
    
19.                 if(land[i][j] == 0){
    
20.                     int res1 = 0;
    
21.                     dfs(land, res1, i, j);
    
22.                     res.push_back(res1);
    
23.                 }
    
24.             }
    
25.         }
    
26.         sort(res.begin(), res.end());
    
27.         return res;
    
28.     }
    
29. };

复制代码

糖逗

下面这种写法为什么会出错？没整明白

1. class Solution {
   
2. private:
   
3.     vector<vector<int> >direct = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
   
4. public:
   
5.     void dfs(vector<vector<int> >&land, int temp, int& res1, int i, int j){
   
6.         if(i < 0 || j < 0 || i >= land.size() || j >= land[0].size() || land[i][j] != 0){
   
7.             res1 = max(res1, temp);
   
8.             return;
   
9.         }
   
10.         for(auto cha : direct){
    
11.             land[i][j] = 3;
    
12.             dfs(land, temp + 1, res1, i + cha[0], j + cha[1]);
    
13.         }
    
14.         
    
15.     }
    
16.     vector<int> pondSizes(vector<vector<int>>& land) {
    
17.         vector<int> res;
    
18.         int len1 = land.size(), len2 = land[0].size();
    
19.         for(int i = 0; i < len1; i++){
    
20.             for(int j = 0; j < len2; j++){
    
21.                 if(land[i][j] == 0){
    
22.                     int res1 = 0;
    
23.                     dfs(land, 0, res1, i, j);
    
24.                     res.push_back(res1);
    
25.                 }
    
26.             }
    
27.         }
    
28.         sort(res.begin(), res.end());
    
29.         return res;
    
30.     }
    
31. };

复制代码