首页 > 代码库 > poj 2386dfs

poj 2386dfs

2024-08-02 09:36:05   224人阅读

Lake Counting
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 20958 Accepted: 10561

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

#include<iostream>#include<cstdlib>#include<cstdio>#include<cstring>#include<string>#include<cmath>#include<algorithm>using namespace std;bool map[101][101];char s[101][101];int ans=0,n,m;int dic[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};void dfs(int l,int t){     int a,b;     for(int i=0;i<8;i++)     {         a=l+dic[i][0],b=t+dic[i][1];         if(a>=0&&a<m&&b>=0&&b<n&&map[a][b]==true)         map[a][b]=false,dfs(a,b);     }}int main(){    scanf("%d%d",&m,&n);    for(int i=0;i<m;i++)    scanf("%s",s[i]);    for(int i=0;i<m;i++)        for(int j=0;j<n;j++)            {                if(s[i][j]==‘W‘)                map[i][j]=true;                else                 map[i][j]=false;            }    for(int i=0;i<m;i++)        for(int j=0;j<n;j++)            if(map[i][j]==true)               map[i][j]=false,ans++,dfs(i,j);    printf("%d\n",ans);    return 0;}

　　

poj 2386dfs


联系
我们