3602 - 查找细胞
一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。
Input
第一行输入n,m;表示n行m列矩阵。
接下来输入该n*m矩阵
Output
细胞个数
Examples
Input
4 10 0234500067 1034560500 2045600671 0000000089
Output
4
Solution C
#include <stdio.h> int dir[4][2]= {0,1,0,-1,1,0,-1,0}; int n,m; int mat[1005][1005]; void dfs(int x,int y) { mat[x][y]=0; int i,tx,ty; for(i=0; i<4; ++i) { tx=x+dir[i][0]; ty=y+dir[i][1]; if(tx<0||tx>=n||ty<0||ty>=m)continue; if(mat[tx][ty])dfs(tx,ty); } } void main() { while(scanf("%d%d",&n,&m)!=EOF) { int ans = 0; int i,j; for(i=0; i<n; ++i) for(j=0; j<m; ++j) scanf("%1d",&mat[i][j]); for(i=0; i<n; ++i) for(j=0; j<m; ++j) if(mat[i][j]) { ++ans; dfs(i,j); } printf("%d\n",ans); } }
Solution C++
#include<iostream> #include<cstring> using namespace std; int n,m,tot=0; char a[101][101]; int dx[]={0,-1,0,1},dy[]={-1,0,1,0}; bool b[101][101]; struct data{ int x,y; }p[1000]; void dfs(int r,int s) { int head,tail; int nx,ny,first=1; head=1;tail=1; p[head].x=r; p[head].y=s; b[r][s]=false; ++tot; while(head<=tail) { for(int i=0;i<4;++i) { nx = p[head].x+dx[i]; ny = p[head].y+dy[i]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&b[nx][ny]==true) { ++tail; p[tail].x=nx; p[tail].y=ny; b[nx][ny]=false; } /*if(head==tail) { for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) cout << b[i][j] << " "; cout << endl; } cout << endl; return; }*/ } ++head; } } int main() { cin >> n >> m; for(int i = 1; i <= n ;++i) for(int j = 1;j <= m; ++j) { cin >> a[i][j]; if(int(a[i][j]-48))b[i][j]=true; else b[i][j]=false; } for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { if(b[i][j]) dfs(i,j); } cout << tot; return 0; }