P1596 [USACO10OCT]Lake Counting S

admin

https://www.luogu.com.cn/problem/P1596

题目描述

由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个NxM(1<=N<=100;1<=M<=100)网格图表示。每个网格中有水('W') 或是旱地('.')。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。

输入格式
第1行：两个空格隔开的整数：N 和 M 第2行到第N+1行：每行M个字符，每个字符是'W'或'.'，它们表示网格图中的一排。字符之间没有空格。
输出格式
一行：水坑的数量

输入输出样例
输入 #1复制

1. 10 12
   
2. W........WW.
   
3. .WWW.....WWW
   
4. ....WW...WW.
   
5. .........WW.
   
6. .........W..
   
7. ..W......W..
   
8. .W.W.....WW.
   
9. W.W.W.....W.
   
10. .W.W......W.
    
11. ..W.......W.

复制代码

输出 #1复制
3

admin

和1451几乎一样，改动8个方向就是。一次AC。

1. #include<iostream>
   
2. using namespace std;
   
3. const int mm=110;
   
4. int m,n,x;
   
5. int a[mm][mm]; ///原始棋盘
   
6. int v[mm][mm]; ///是否被访问
   
7. int dr[]= {0,+1,+1,+0,-1,-1,-1,+0,+1};
   
8. int dc[]= {0,+0,+1,+1,+1,+0,-1,-1,-1};
   
9. void check()  ///检查a数组和v数组
   
10. {
    
11.         for (int r=1; r<=m; r++,cout<<endl)
    
12.                 for (int c=1; c<=n; c++) cout<<a[r][c];
    
13.         for (int r=1; r<=m; r++,cout<<endl)
    
14.                 for (int c=1; c<=n; c++) cout<<v[r][c];
    
15. }
    
16. void dfs(int r ,int c,int x) ///从rc处开始给区域染色为x
    
17. {
    
18.         a[r][c]=x,v[r][c]=1;
    
19.         ///cout<<r<<' '<<c<<endl;check();int y;cin>>y;
    
20.         for (int i=1; i<=8; i++)
    
21.                 {
    
22.                         int tr=r+dr[i],tc=c+dc[i];
    
23.                         if (a[tr][tc]!=0 && v[tr][tc]==0)dfs(tr,tc,x);
    
24.                 }
    
25. }
    
26. 
    
27. int main()
    
28. {
    
29.         cin>>m>>n;
    
30.         for (int r=1; r<=m; r++)
    
31.                 for (int c=1; c<=n; c++)
    
32.                         {
    
33.                                 char ch;cin>>ch;
    
34.                                 a[r][c]=(ch=='W');
    
35.                         }
    
36.         for (int r=1; r<=m; r++)
    
37.                 for (int c=1; c<=n; c++)
    
38.                         if (a[r][c]!=0 && v[r][c]==0) dfs(r,c,++x);
    
39. //check();
    
40.         cout<<x;
    
41.         return 0;
    
42. }
    
43. 
    
44. /*
    
45. 10 12
    
46. W........WW.
    
47. .WWW.....WWW
    
48. ....WW...WW.
    
49. .........WW.
    
50. .........W..
    
51. ..W......W..
    
52. .W.W.....WW.
    
53. W.W.W.....W.
    
54. .W.W......W.
    
55. ..W.......W.
    
56. */

复制代码