细胞——求细胞数量 C++详解

求细胞数量

题目描述

一矩形阵列由数字 $0$ 到 $9$ 组成，数字 $1$ 到 $9$ 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

输入格式

第一行两个整数代表矩阵大小 $n$ 和 $m$。

接下来 $n$ 行，每行一个长度为 $m$ 的只含字符 0 到 9 的字符串，代表这个 $n\times m$ 的矩阵。

输出格式

一行一个整数代表细胞个数。

样例

样例输入

4 10
0234500067
1034560500
2045600671
0000000089

样例输出

4

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1\le n,m\le 100$。

解法

暴力搜索就好了

代码

#include <bits/stdc++.h>
using namespace std;
short a[1000][1000];
int n,m,s;
string t;
void laiba(int i,int j)
{if (a[i][j]==0) return;a[i][j]=0;laiba(i-1,j);laiba(i,j-1);laiba(i+1,j);laiba(i,j+1);
}
int main ()
{cin >>n >>m;for (int i=1;i<=n;i++){cin >>t;for (int j=1;j<=m;j++){a[i][j]=t[j-1]-48;}}for (int i=1;i<=n;i++){for (int j=1;j<=m;j++){if (a[i][j]){s++;laiba(i,j);}}}cout <<s;return 0;
}