首页 > 代码库 > BZOJ 3385: [Usaco2004 Nov]Lake Counting 数池塘
BZOJ 3385: [Usaco2004 Nov]Lake Counting 数池塘
题目
3385: [Usaco2004 Nov]Lake Counting 数池塘
Time Limit: 1 Sec Memory Limit: 128 MBDescription
农夫约翰的农场可以表示成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.
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
HINT
共有3个池塘:一个在左上角,一个在左下角,还有一个沿着右边界
题解
我用floodfill做的,呵呵,时间Rank倒数第一= =
代码
1 /*Author:WNJXYK*/ 2 #include<cstdio> 3 #include<iostream> 4 using namespace std; 5 int n,m; 6 const int Maxn=100; 7 bool map[Maxn+10][Maxn+10]; 8 bool visited[Maxn+10][Maxn+10]; 9 inline char read(){10 char ch=getchar();11 while(ch!=‘.‘ && ch!=‘W‘) ch=getchar();12 return ch;13 } 14 int cnt=0;15 int dx[]={0,-1,-1,0,1,1,1,0,-1};16 int dy[]={0,0,1,1,1,0,-1,-1,-1};17 void floodfill(int x,int y){18 visited[x][y]=true;19 for (int k=1;k<=8;k++){20 int nx=x+dx[k],ny=y+dy[k];21 if (1<=nx && nx<=n && 1<=ny && ny<=m)22 if (map[nx][ny]==true)23 if (visited[nx][ny]==false)24 floodfill(nx,ny);25 }26 }27 28 int main(){29 scanf("%d%d",&n,&m);30 for (int i=1;i<=n;i++){31 for (int j=1;j<=m;j++){32 char ch=read();33 if (ch==‘.‘) map[i][j]=false;34 if (ch==‘W‘) map[i][j]=true;35 visited[i][j]=false;36 }37 }38 for (int i=1;i<=n;i++){39 for (int j=1;j<=m;j++){40 if (visited[i][j]==false&&map[i][j]==true){41 floodfill(i,j);42 cnt++;43 } 44 } 45 }46 printf("%d\n",cnt);47 return 0;48 }
BZOJ 3385: [Usaco2004 Nov]Lake Counting 数池塘
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。