百道经典算法题——水域大小

百道经典算法题——水域大小

计算水域中池塘大小并排序打印

你有一个用于表示一片土地的整数矩阵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

解法详谈：

本题为求水域问题，与其类似的有求岛屿问题，问题的核心在于使用深度优先遍历（DFS）进行求解水池大小及个数，返回时进行qsort排序。熟练掌握DFS、BFS算法是解决此类问题的关键。DFS、BFS算法有递归算法以及非递归算法，非递归算法分别借助相应的数据结构实现 [ DFS-> 栈；BFS->队列 ]。本题求解时使用递归算法，那么在使用递归算法时，一定要做好对递归出口的把握，例如本题中递归出口即为：1、坐标非合法区域；2、非水域位置

/*** Note: The returned array must be malloced, assume caller calls free().*/
static int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,-1},{-1,1}};
int compare (const void * a, const void * b)
{return ( *(int*)a - *(int*)b );  //这里的数组元素类型为int
}
int searchPoud(int** land, int landSize, int q, int p){if(p<0||q<0||p>=landSize||q>=landSize)  return 0;if(land[q][p] != 0) return 0;land[q][p] = 1;int size = 1;for(int i = 0;i<8;i++)size += searchPoud(land,landSize,q+dir[i][0],p+dir[i][1]);return size;
}
int* pondSizes(int** land, int landSize, int* landColSize, int* returnSize){int* ans = (int*)malloc(sizeof(int)*landSize*landSize);int count = 0;for(int i = 0;i<landSize*landSize;i++)ans[i] = landSize*landSize;for(int q = 0;q<landSize;q++)for(int p = 0;p<landSize;p++)if(land[q][p] == 0){int size = searchPoud(land,landSize,q,p);ans[count++] = size;}int* result = (int*)malloc(sizeof(int)*count);qsort (ans, landSize*landSize, sizeof(int), compare);for(int l = 0;l<count;l++){result[l] = ans[l];}*returnSize = count;return result;
}

使用C语言求解相关算法时，对于二维数组的参数传递需要注意，在分配内存是有静态以及动态的区分，对于动态分配时，要注意二维数组的建立、传递问题，以及相关的指针知识以及对分配时内存的使用。问题~可以查看文章——C二维数组动态分配，参数传递