《程序员面试金典（第6版）》面试题 16.19. 水域大小（深度优先搜索，类似棋盘类问题，八皇后的简化版本，C++）

题目描述

你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。

示例：

输入：
[[0,2,1,0],[0,1,0,1],[1,1,0,1],[0,1,0,1]
]
输出： [1,2,4]

提示：

• 0 < len(land) <= 1000
• 0 < len(land[i]) <= 1000

原题链接

解题思路与代码

首先，这道题是一道有意思的思考题，有点类似于棋盘类的题型了。

一上来大家可能有点懵，但是仔细想想或者看过题目下面的相关提示后，可能就会想，哦，这道题我们可以用深度优先搜索去做呀~

其实在做这道题的过程中，我感觉这道题可以算是一道类似棋盘类的问题了，可以说可以算是八皇后的简单版本。因为我们同样要去设置一个标记数组，去记录某一个格子是否已经被记录过了。也要检查多个方向等。

言归正传，让我们来讲解一下这道题到底是如何用深度搜索做的。

• 首先让我们创建一个记录结果的数组，result，一个二维标记数组visit。
• 准备好之后，我们开始用双层for循环，从左到右从上到下的去遍历每一个棋子。
• 只有当这个棋子在land中被记录为0，并且没有被标记数组标记过，我们才能进入这个棋子的递归。
• 这个递归函数会检查一个棋子的8个方向上都有没有池塘，如果有，则标记这个棋子，最后返回一个int值，代表这个池塘有多少块水域。
• 我们会把这个池塘添加到result中去，最后把result排个序，之后返回就可以了。

具体代码如下：

class Solution {
public:vector<int> pondSizes(vector<vector<int>>& land) {vector<int> result;int m = land.size();int n = land[0].size();vector<vector<bool>> visit(m,vector<bool>(n,false));for(int i = 0; i < m; ++i)for(int j = 0; j < n; ++j)if(land[i][j] == 0 && !visit[i][j]){int size = dfs(land,visit,i,j);result.push_back(size);}sort(result.begin(),result.end());return result;}int dfs(vector<vector<int>>& land, vector<vector<bool>>& visit,int i, int j){if(i < 0 || j < 0 || i >= land.size() || j >=land[0].size() || land[i][j] != 0 || visit[i][j])return 0;int size = 1;visit[i][j] = true;for(int r = -1; r <= 1; ++r)for(int c = -1; c <= 1; ++c)size += dfs(land,visit,i + r,j + c);return size;}
};

复杂度分析

时间复杂度：

• 在最坏的情况下，我们需要遍历土地矩阵中的每个单元格，并可能需要进行深度优先搜索。因此，时间复杂度为O(n^2)。

空间复杂度：

• 我们需要一个与土地矩阵大小相同的visited矩阵来跟踪每个单元格是否已被访问。此外，由于我们使用了递归，因此还需要考虑调用堆栈的空间。在最坏的情况下，可能需要进行m*n次递归调用（例如，当所有单元格都是水域时）。因此，空间复杂度也为O(n^2)。

当我们说深度优先搜索的时间复杂度是O(n^2)时，我们是指最坏的情况下，我们需要访问土地矩阵中的每一个单元格。在这个过程中，每个单元格可能会被DFS函数访问多次（最多9次，包括自身和周围的8个邻居），但是每个单元格只会被处理（即被加入到某个池塘的大小中）一次，因为一旦一个单元格被处理，我们就会将其标记为已访问，之后就不会再处理它了。

因此，虽然DFS函数可能会被调用多于n^2 次，但是我们只需要进行n^2 次实际的处理，所以时间复杂度仍然是O(n^2)。

总结

• 这道题目主要是为了考察求解者对深度优先搜索（DFS）和图遍历的理解和应用能力。

• 在实际应用中，这种类型的问题可能出现在一些地理信息系统（GIS）或者环境科学的领域，比如：

  • 水体识别和测量：这个问题可以用于识别和测量地图上的水体。给定一张地形图（通过海拔高度表示），我们可以计算出地图上水体（海拔高度为0的区域）的数量和大小。

  • 连通区域识别：在计算机视觉或图像处理中，这个问题可以用于识别图像中的连通区域。例如，我们可以使用类似的方法来识别和测量图像中的特定颜色或纹理的区域。

  • 地图路径规划：这个问题也可以用于规划地图上的路径。例如，我们可以使用DFS来寻找从一点到另一点的路径，或者寻找所有可以到达的点。

通过这道题，你可以加深对深度优先搜索（DFS）算法的理解，这对于很多图论问题和搜索问题的解决都是非常有帮助的。

最后的最后，如果你觉得我的这篇文章写的不错的话，请给我一个赞与收藏，关注我，我会继续给大家带来更多更优质的干货内容。