Lake Counting(水洼计数)

题目

有一个大小为N*M的园子,寻找水洼个数量

题目解析

  • 用数组来表示园子
  • 对园子的遍历是具有八个方向的(八连通)
  • 因此,临近的定义为:从某点能一步到达另一点,这称为两点邻近
  • W代表积水,.代表非积水
  • 水洼的定义: 被非积水包围着的大积水

解题思路

  • 逐一遍历数组
  • 当值为w时,进行深度优先遍历,将邻近的w变成.,当没有临近的w时,遍历结束
  • 因此,假设从A的进行dfs遍历,则能保证能将A所在的水洼变成.
  • 因此,进入DFS遍历的次数水洼的个数
  • 时间复杂度为O(8*M*N)

    代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
using namespace std;

//输入
int N = 10;
int M = 12;
char field[10][12] = {
'w','.','.','.','.','.','.','.','.','w','w','.',
'.','w','w','w','.','.','.','.','.','w','w','w',
'.','.','.','.','w','w','.','.','.','.','.','.',
'.','.','.','.','.','.','.','.','.','.','.','.',
'.','.','.','.','.','.','.','.','.','.','.','.',
'.','.','w','.','.','.','.','.','.','.','.','.',
'.','w','w','w','.','.','.','.','.','.','w','.',
'w','w','w','.','.','.','.','.','.','.','.','.',
'.','w','.','.','.','.','.','.','.','.','.','.',
'.','.','.','.','.','.','.','.','.','.','.','.'
};

void dfs(int x,int y){
if (x<0 || x>=N || y<0 || y>=M){
return ;
}
// 遍历八个方向
for (int i=-1;i<2;i++){
for (int j=-1;j<2;j++){
int x_tmp = x+i;
int y_tmp = y+j;
if(x_tmp<0 || x_tmp>=N || y_tmp<0 || y_tmp>=M) continue;
if ( field[x_tmp][y_tmp]=='w'){
field[x_tmp][y_tmp]='.';
dfs(x_tmp,y_tmp);
}
}
}
return ;
}

int main() {
int count = 0;
for (int i=0;i<10;i++){
for (int j=0;j<12;j++) {
// 当遇到积水时,进入dfs遍历
if(field[i][j]=='w'){
dfs(i, j);
count++;
}

}
}
cout<<count<<endl;
return 0;
}

结果

1
4

本文标题:Lake Counting(水洼计数)

文章作者:定。

发布时间:2017年8月25日 - 09时08分

本文字数:1,878字

原始链接:http://cocofe.cn/2017/08/25/Lake Counting(水洼计数)/

许可协议: Attribution-NonCommercial 4.0

转载请保留以上信息。