华师一附中OI组

标题: P1451 求细胞数量 [打印本页]
作者: admin    时间: 2018-5-12 23:02
标题: P1451 求细胞数量
https://www.luogu.org/problemnew/show/P1451

题目描述
一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。（1<=m,n<=100）?

输入输出格式
输入格式：
输入：整数m,n(m行，n列)

矩阵

输出格式：
输出：细胞的个数

输入输出样例
输入样例#1：
4  10
0234500067
1034560500
2045600671
0000000089
输出样例#1：
4
作者: admin    时间: 2019-10-27 17:49
典型的种子填充算法，直观的用两个二维数组，一个a表示当前的棋盘，一个v表示是否被访问过，然后每行每列逐个扫描填充。
  1. #include<iostream>
  2. using namespace std;
  3. const int mm=110;
  4. int m,n,x;
  5. char ch;
  6. int a[mm][mm]; ///原始棋盘
  7. int v[mm][mm]; ///是否被访问
  8. int dr[]= {0,+1,+0,-1,+0};
  9. int dc[]= {0,+0,+1,+0,-1}; ///下右上左
  10. void check()  ///检查a数组和v数组
  11. {
  12.         for (int r=1; r<=m; r++,cout<<endl)
  13.                 for (int c=1; c<=n; c++) cout<<a[r][c];
  14.         for (int r=1; r<=m; r++,cout<<endl)
  15.                 for (int c=1; c<=n; c++) cout<<v[r][c];
  16. }
  17. void bfs(int r ,int c,int x) ///从rc处开始给区域染色为x
  18. {
  19.         ///cout<<r<<' '<<c<<' '<<x<<endl;
  20.         int qr[mm*mm],qc[mm*mm]; ///队列，注意空间大小
  21.         int h=1,t=2;
  22.         qr[h]=r,qc[h]=c,v[r][c]=x;///队头染色
  23.         while (h<t)
  24.                 {
  25.                         for (int i=1; i<=4; i++)
  26.                                 {
  27.                                         int tr=qr[h]+dr[i],tc=qc[h]+dc[i];
  28.                                         if (a[tr][tc]!=0 && v[tr][tc]==0)
  29.                                                 {
  30.                                                         v[tr][tc]=x;
  31.                                                         qr[t]=tr,qc[t]=tc,t++;
  32.                                                 }
  33.                                 }
  34.                         h++;
  35.                 }
  36. }
  37. int main()
  38. {
  39.         cin>>m>>n;
  40.         for (int r=1; r<=m; r++)
  41.                 for (int c=1; c<=n; c++)
  42.                         {
  43.                                 cin>>ch;
  44.                                 a[r][c]=ch-'0';
  45.                         }
  46.         for (int r=1; r<=m; r++)
  47.                 for (int c=1; c<=n; c++)
  48.                         if (a[r][c]!=0 && v[r][c]==0) bfs(r,c,++x);
  49.         ///check();
  50.         cout<<x;
  51.         return 0;
  52. }

  54. /*
  55. 4  10
  56. 0234500067
  57. 1034560500
  58. 2045600671
  59. 0000000089
  60. */
复制代码
作者: admin    时间: 2019-10-27 17:53
此题是我爱说的全搜索的题目，棋盘上的每一个点都要被搜到，所以可以用BFS也可以用DFS，为一个区别就是主程序的二维循环中bfs改成dfs，而且，要是dfs的话是不是有点像tarjar算法？那么来一个DFS版本的吧
  1. #include<iostream>
  2. using namespace std;
  3. const int mm=110;
  4. int m,n,x;
  5. char ch;
  6. int a[mm][mm]; ///原始棋盘
  7. int v[mm][mm]; ///是否被访问
  8. int dr[]= {0,+1,+0,-1,+0};
  9. int dc[]= {0,+0,+1,+0,-1}; ///下右上左
  10. void check()  ///检查a数组和v数组
  11. {
  12.         for (int r=1; r<=m; r++,cout<<endl)
  13.                 for (int c=1; c<=n; c++) cout<<a[r][c];
  14.         for (int r=1; r<=m; r++,cout<<endl)
  15.                 for (int c=1; c<=n; c++) cout<<v[r][c];
  16. }
  17. void dfs(int r ,int c,int x) ///从rc处开始给区域染色为x
  18. {
  19.         a[r][c]=x,v[r][c]=1;
  20.         ///cout<<r<<' '<<c<<endl;check();int y;cin>>y;
  21.         for (int i=1; i<=4; i++)
  22.                 {
  23.                         int tr=r+dr[i],tc=c+dc[i];
  24.                         if (a[tr][tc]!=0 && v[tr][tc]==0)dfs(tr,tc,x);
  25.                 }
  26. }

  28. int main()
  29. {
  30.         cin>>m>>n;
  31.         for (int r=1; r<=m; r++)
  32.                 for (int c=1; c<=n; c++)
  33.                         {
  34.                                 cin>>ch;
  35.                                 a[r][c]=ch-'0';
  36.                         }
  37.         for (int r=1; r<=m; r++)
  38.                 for (int c=1; c<=n; c++)
  39.                         if (a[r][c]!=0 && v[r][c]==0) dfs(r,c,++x);
  40.         ///check();
  41.         cout<<x;
  42.         return 0;
  43. }

  45. /*
  46. 4  10
  47. 0234500067
  48. 1034560500
  49. 2045600671
  50. 0000000089
  51. */
复制代码






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