P1451 求细胞数量

admin

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

典型的种子填充算法，直观的用两个二维数组，一个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. }
    
53. 
    
54. /*
    
55. 4  10
    
56. 0234500067
    
57. 1034560500
    
58. 2045600671
    
59. 0000000089
    
60. */

复制代码

admin

此题是我爱说的全搜索的题目，棋盘上的每一个点都要被搜到，所以可以用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. }
    
27. 
    
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. }
    
44. 
    
45. /*
    
46. 4  10
    
47. 0234500067
    
48. 1034560500
    
49. 2045600671
    
50. 0000000089
    
51. */

复制代码