BZOJ 3385: [Usaco2004 Nov]Lake Counting 数池塘

题目

3385: [Usaco2004 Nov]Lake Counting 数池塘

Time Limit: 1 Sec Memory Limit: 128 MB

Description

农夫约翰的农场可以表示成N×M(1≤N，M≤100)个方格组成的矩形．由于近日的降雨，

在约翰农场上的不同地方形成了池塘．每一个方格或者有积水(’W’)或者没有积水(’．’)．农夫约翰打算数出他的农场上共形成了多少池塘．一个池塘是一系列相连的有积水的方格，每一个方格周围的八个方格都被认为是与这个方格相连的．

现给出约翰农场的图样，要求输出农场上的池塘数．

Input

第1行：由空格隔开的两个整数N和M．

第2到N+1行：每行M个字符代表约翰农场的一排方格的状态．每个字符或者是’W’或者

是’．’，字符之间没有空格．

Output

约翰农场上的池塘数．

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

HINT

共有3个池塘：一个在左上角，一个在左下角，还有一个沿着右边界

题解

我用floodfill做的，呵呵，时间Rank倒数第一= =

代码

 /*Author:WNJXYK*/

 #include<cstdio>

 #include<iostream>

 using namespace std;

 int n,m;

 const int Maxn=;

 bool map[Maxn+][Maxn+];

 bool visited[Maxn+][Maxn+];

 inline char read(){

     char ch=getchar();

     while(ch!='.' && ch!='W') ch=getchar();

     return ch;

 }

 int cnt=;

 int dx[]={,-,-,,,,,,-};

 int dy[]={,,,,,,-,-,-};

 void floodfill(int x,int y){

     visited[x][y]=true;

     for (int k=;k<=;k++){

         int nx=x+dx[k],ny=y+dy[k];

         if (<=nx && nx<=n && <=ny && ny<=m)

             if (map[nx][ny]==true)

                 if (visited[nx][ny]==false)

                     floodfill(nx,ny);

     }

 }

 int main(){

     scanf("%d%d",&n,&m);

     for (int i=;i<=n;i++){

         for (int j=;j<=m;j++){

             char ch=read();

             if (ch=='.') map[i][j]=false;

             if (ch=='W') map[i][j]=true;

             visited[i][j]=false;

         }

     }

     for (int i=;i<=n;i++){

         for (int j=;j<=m;j++){

             if (visited[i][j]==false&&map[i][j]==true){

                 floodfill(i,j);

                 cnt++;

             }

         }

     }

     printf("%d\n",cnt);

     return ;

 }

秒客网