题目
描述
一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。(1<=m,n<=100)?
输入输出格式
输入格式:
输入:整数m,n(m行,n列)
矩阵
输出格式:
输出:细胞的个数
输入输出样例
输入样例#1:
4 10
0234500067
1034560500
2045600671
0000000089
输出样例#1:
4
思路
这道题目实质上就是一个找连通块的问题,输入完成之后把整个矩阵遍历一遍,遇到不是0的就ans++,然后把它周围八个方块与它相同的全部改成0,直到没有再和它相同的为止。用搜索来做,广搜深搜都可以。
代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m; 4 int ans; 5 char a[105][105]; 6 voID dfs(int x,int y) 7 { 8 if(x>n||x<1||y>m||y<1||a[x][y]==‘0‘)return; 9 a[x][y]=‘0‘;10 dfs(x+1,y);11 dfs(x,y+1);12 dfs(x-1,y);13 dfs(x,y-1);14 }15 int main()16 {17 cin>>n>>m;18 for(int i=1;i<=n;i++)19 {20 for(int j=1;j<=m;j++) cin>>a[i][j];21 }22 for(int i=1;i<=n;i++)23 {24 for(int j=1;j<=m;j++)25 {26 if(a[i][j]!=‘0‘)ans++,dfs(i,j);27 }28 }29 cout<<ans<<endl;30 return 0;31 }总结
以上是内存溢出为你收集整理的【题解】求细胞数量-C++全部内容,希望文章能够帮你解决【题解】求细胞数量-C++所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)