Pond Sizes: You have an integer matrix representing a plot of land, where the value at that loca tion represents the height above sea level. A value of zero indicates water. A pond is a region of water connected vertically, horizontally, or diagonally. The size of the pond is the total number of connected water cells. Write a method to compute the sizes of all ponds in the matrix.
EXAMPLE
1
2
3
4
5
6
|
Input:
0 2 1 0
0 1 0 1
1 1 0 1
0 1 0 1
Output: 2, 4, 1 (in any order)
|
Hints: #674, #687, #706, #723
解法
一个矩阵，里面有数字，0则代表水，池塘则是相连的水组成（横着连、纵着连、斜着连），池塘大小则是水的数量。
例子里给出Output则是这么几个池塘：
1
2
3
4
|
[0] 2 1 [0]
[0] 1 [0] 1
1 1 [0] 1
[0] 1 [0] 1
|
解决思路可以是这样的：
- 按照从左到右，从上到下的顺序，来遍历数组，当遇到0的时候则进入池塘搜索模式
- 池塘搜索模式：
- 池塘初始大小为1，把当前cell设置为-1（标记为已经记录过）
- 碰到非0则退出
- 向右、向左、向下、向左下、向右下搜索，重复1-3步
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
public void pondSizes(int[][] land) {
int rows = land.length;
int cols = land[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (land[i][j] == 0) {
int pondSize = searchPond(land, i, j);
if (pondSize != 0) {
System.out.println(pondSize);
}
}
}
}
}
private int searchPond(int[][] land, int r, int c) {
// 超出边界
if (r >= land.length || c >= land[0].length || r < 0 || c < 0) {
return 0;
}
if (land[r][c] != 0) {
return 0;
}
land[r][c] = -1;
int pondSize = 1;
// 往右边找
pondSize += searchPond(land, r, c + 1);
// 往左边找
pondSize += searchPond(land, r, c - 1);
// 往下边找
pondSize += searchPond(land, r + 1, c);
// 往左下找
pondSize += searchPond(land, r + 1, c - 1);
// 往右下找
pondSize += searchPond(land, r + 1, c + 1);
return pondSize;
}
|
时间复杂度：O(N2)，N是NxN矩阵的N。思路：pondSizes方法遍历了整个矩阵，因此是N2。searchPond方法看似也遍历了整个矩阵，但是当它真的遍历了整个矩阵就意味着矩阵里都是0，那么下一次它就不会被调用了。也就是每个0 cell只会被touch一次，第二次的时候就跳过了。
评论