2622 - 细胞
一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如阵列:
0234500067103456050020456006710000000089有4个细胞。
Input
整数m,n(m行，n列)矩阵
Output
细胞的个数。
Examples
Input
4 10 0234500067 1034560500 2045600671 0000000089
Output
4
Solution C++
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int a[100][100],ans,m,n; const int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; struct queh { int x,y; }que[100*100]; void init() { cin>>m>>n; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) scanf("%1d",&a[i][j]); } } void bfs(int x,int y) { int head=0,tail=1; que[head].x=x,que[head].y=y; a[x][y]=0; while(head!=tail) { for(int i=0;i<4;i++) { int nx=que[head].x+dx[i],ny=que[head].y+dy[i]; if(a[nx][ny]&&nx>0&&ny>0&&nx<=m&&ny<=n) { //add(nx,ny); queh t; t.x=nx,t.y=ny; que[tail++]=t; a[nx][ny]=0; } } head++; } } void print() { printf("%d",ans); } int main() { init(); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(a[i][j]!=0){ bfs(i,j); ans++; } print(); return 0; }