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 <stdio.h> char M[101][101]; int Used[101][101]; int direction[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; int i,j,p; int col,row; int iCount=0; void DFS(int x,int y) { int k; for(k=0;k<8;k++) { int tx= x+direction[k][0]; int ty= y+direction[k][1]; if(tx >= 0 && tx < row && ty >= 0 && ty < col && M[tx][ty] == 'W' && Used[tx][ty]==0) { Used[tx][ty]=1; DFS(tx,ty); } } } int main() { scanf("%d%d",&row,&col); for(i=0;i<row;i++) scanf("%s",M[i]); for(i=0;i<row;i++) { for(j=0;j<col;j++) { if(M[i][j]=='W' && Used[i][j] == 0) { Used[i][j]=1; //将其本身赋为已访问过(注意:这一点容易被忽略) DFS(i,j); iCount++; } } } printf("%d\n",iCount); }转载于:https://www.cnblogs.com/o8o8o888/archive/2011/08/19/2145644.html
