poj 2386 Lake Counting dfs

缘起

日常水题 poj 2386 Lake Counting

分析

题意很裸

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
由于最近的降雨，水汇集在Farmer John's田地的不同地方，其由N×M（1 <= N <= 100; 1 <= M <= 100）的正方形矩形
表示。 每个方块包含水（'W'）或旱地（'.'）。 农夫约翰想弄清楚他的田地里有多少个池塘。 池塘是一组连接的正方
形，其中有水，其中一个正方形被认为与其所有八个邻居相邻。

给出农夫约翰的田地图，确定他有多少池塘。

【输入】
*第1行：两个以空格分隔的整数：N和M.

*行 2..N + 1：每行M个字符代表一行Farmer John的字段。 每个字符都是'W'或'.'。 字符之间没有空格

【输出】
第1行：Farmer John的田地里的池塘数量

【样例输入】
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

【样例输出】
3

【提示】
样例输入有三个池塘：一个在左上角，一个在左下角，一个在右侧。

【限制】
Time limit 1000 ms
Memory limit 65536 kB

dfs裸题, 即所谓的泛洪算法（floodfill）

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
54
55
56
57
58
59
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL

int n,m,cnt;
bool isvisit[105][105];
char a[105][105];
const int next[8][2] = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}}; // 8个方向

bool ok(int x, int y) // (x,y)合法吗?
{
	return ~x&&x<n&&~y&&y<m&&a[x][y]=='W'&&!isvisit[x][y]; // 不越界并且是水而且没访问过才合法
}

void dfs(int x, int y) // 从 (x,y)开始泛洪
{
	isvisit[x][y] = true;
	for (int i = 0;i<8;i++) // 沿着8个方向走位
	{
		int nx = x+next[i][0];
		int ny = y+next[i][1];
		if (ok(nx,ny))
		{
			dfs(nx,ny);
		}
	}
}

int main() 
{

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	scanf("%d%d", &n, &m);
	getchar(); // 吸收多余换行符
	for (int i = 0; i<n; i++)
	{
		for (int j = 0; j<m; j++)
		{
			a[i][j] = getchar();
		}
		getchar();
	}
	for (int i = 0; i<n; i++)
	{
		for (int j = 0; j< m ;j++)
		{
			if (!isvisit[i][j]&&a[i][j]=='W')
			{
				cnt++;
				dfs(i,j);
			}
		}
	}
	printf("%d\n", cnt);
	return 0;
}

ac情况

Status Accepted
Memory 372kB
Length 919
Lang C++
Submitted 2019-08-15 15:25:55
Shared
RemoteRunId 20744196