# POJ2386 Lake Counting 【DFS】

2022年11月23日
0 收藏 477 点赞 2,874 浏览 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 12W........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模块及安装方法

Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…

zengkefu@server1:/usr/src\$ uname -aLinux server1 4.10.0-19-generic #21…

Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…

Struts的使用