首页 > 代码库 > TYVJ 1127 计算细胞数(DFS)

TYVJ 1127 计算细胞数(DFS)

2024-07-15 14:18:13   222人阅读

计算细胞数

From 陈超锐
 
描述 Description
一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。 

如:阵列 

0234500067 
1034560500 
2045600671 
0000000089　　 
有４个细胞 
 
输入格式 InputFormat
第一行　：两个数字M N （1<=Ｍ<=50 1<=N<80）表示该阵列有Ｍ行Ｎ列　 
从第２行到第Ｍ＋１行　每行有连续的Ｎ个字符 
 
输出格式 OutputFormat
一行: 细胞个数
 
样例输入 SampleInput 

4 10
0234500067
1034560500
2045600671
0000000089

 

样例输出 SampleOutput 
4
 
来源 Source
(陈超锐提供)
 
DFS水题，统计连通区域
 1 #include<cstdio> 2 #include<cstring> 3 #include<stdlib.h> 4 #include<algorithm> 5 using namespace std; 6 char a[55][85]; 7 int vis[55][85]; 8 int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; 9 int n,m,cnt;10 void DFS(int x,int y)11 {12     for(int i=0;i<4;i++)13     {14         int xx=x+dir[i][0];15         int yy=y+dir[i][1];16         if(!vis[xx][yy]&&a[xx][yy]!=‘0‘&&0<=xx&&xx<n&&0<=yy&&yy<m)17         {18             vis[xx][yy]=1;19             DFS(xx,yy);20         }21     }22     return ;23 }24 int main()25 {26     scanf("%d %d",&n,&m);27     for(int i=0;i<n;i++)28         scanf("%s",a[i]);29     for(int i=0;i<n;i++)30         for(int j=0;j<m;j++)31             if(a[i][j]!=‘0‘&&!vis[i][j])32             {33                 DFS(i,j);34                 cnt++;35             }36     printf("%d\n",cnt);37     return 0;38 }
View Code

 


联系
我们