首页 > 代码库 > POJ 2386

POJ 2386

2024-11-10 16:13:02   203人阅读

题目：

Lake Counting
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 21515 Accepted: 10831

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

解题思路：简单的深度优先搜索。

代码：

#include<iostream>
using namespace std;
#define	MAX_N 105
int N,M;
char field[MAX_N][MAX_N + 1]; //园子

//现在位置（x,y）
void dfs(int x, int y){
	//将现在所在位置替换为 '.'。
	field[x][y] = '.';
	//循环遍历移动的8个方向
	for(int dx=-1; dx<=1; dx++){
		for(int dy=-1; dy<=1; dy++){
			//向x方向移动dx， 向y方向移动dy，移动的结果为(nx,ny)
			int nx = x + dx, ny = y + dy;
			//判断(nx,ny)是不是在园子内，以及是否有积水
			if(0<=nx && nx<N && 0<=ny && ny<M && field[nx][ny] == 'W')
				dfs(nx,ny);
		}	
	}
	return;
}


void solve(){
	int res = 0;
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			if(field[i][j] == 'W'){
				//从有W的地方开始dfs
				dfs(i,j);
				res ++;
			}
		}
	}
	printf("%d\n",res);
}

int main(){
	//freopen("input.txt","r",stdin);  
    //freopen("output.txt","w",stdout); 
	int i,j;
	while(cin>>N>>M){
		for(i=0; i<N; i++){
			for(j=0; j<M; j++){
				cin>>field[i][j];
			}
		}
		solve();
	}
	return 0;
}


POJ 2386


联系
我们