TYVJ 1127 计算细胞数(DFS)

计算细胞数

描述 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

来源 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
",cnt);
37     return 0;
38 }

View Code