华师一附中OI组

标题: P1596 [USACO10OCT]Lake Counting S [打印本页]
作者: admin    时间: 2021-5-17 16:33
标题: P1596 [USACO10OCT]Lake Counting S
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    时间: 2021-5-17 16:36
和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. }

  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. }

  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. */
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2