首页 技术 正文
技术 2022年11月23日
0 收藏 477 点赞 2,808 浏览 1505 个字

Lake Counting

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 20782   Accepted: 10473

Description

Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (‘.’). Farmer John would like to figure
out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors. 

Given a diagram of Farmer John’s field, determine how many ponds he has.

Input

* Line 1: Two space-separated integers: N and M 

* Lines 2..N+1: M characters per line representing one row of Farmer John’s field. Each character is either ‘W’ or ‘.’. The characters do not have spaces between them.

Output

* Line 1: The number of ponds in Farmer John’s field.

Sample Input

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

Sample Output

3

Hint

OUTPUT DETAILS: 

There are three ponds: one in the upper left, one in the lower left,and one along the right side.

Source

USACO 2004 November

睡前水一水。

#include <stdio.h>
#include <string.h>#define maxn 102char G[maxn][maxn];
int n, m;
const int mov[][2] = {0, 1, 0, -1, 1, 0, -1,
0, 1, -1, -1, 1, 1, 1, -1, -1};void DFS(int x, int y) {
G[x][y] = '.';
int i, j, nx, ny;
for(i = 0; i < 8; ++i) {
nx = x + mov[i][0];
ny = y + mov[i][1];
if(nx >= 0 && nx < n && ny >= 0 && ny < m && G[nx][ny] == 'W')
DFS(nx, ny);
}
}int main() {
int i, j, ret;
while(scanf("%d%d", &n, &m) == 2) {
for(i = 0; i < n; ++i)
scanf("%s", G[i]);
ret = 0;
for(i = 0; i < n; ++i)
for(j = 0; j < m; ++j)
if(G[i][j] == 'W') {
DFS(i, j);
++ret;
}
printf("%d\n", ret);
}
return 0;
}

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:8,910
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,435
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,250
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,061
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,693
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,731