求细胞数量（联通图，宽搜，深搜）

题目描述

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

输入格式

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

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

输出格式

一行一个整数代表细胞个数。 输入输出样例

输入 #1

4 10 0234500067 1034560500 2045600671 0000000089

输出 #1

4

说明/提示 数据规模与约定

对于 100% 的数据，保证1≤n,m≤100。

#include<cstdio> #include<iostream> #include<queue> using namespace std; string mp[105]; bool vis[105][105]; int vir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; int n,m,ans; bool is_shuzi(char str){ return str>='1'&&str<='9'; } //深搜实现 void dfs(int x,int y){ for(int i=0;i<4;i++){ int tx=vir[i][0]+x; int ty =vir[i][1]+y; if(tx>=0&&tx<n&&ty>=0&&ty<m&&!vis[tx][ty]&&is_shuzi(mp[tx][ty])){ vis[tx][ty]=true; dfs(tx,ty); } } } //宽搜实现 void bfs(int x,int y){ queue<pair<int,int> > que; que.push(make_pair(x,y)); vis[x][y]=true; while(!que.empty()){ for(int i=0;i<4;i++){ int tx = que.front().first+vir[i][0]; int ty = que.front().second+vir[i][1]; if(tx>=0&&tx<n&&ty>=0&&ty<m&&!vis[tx][ty]&&is_shuzi(mp[tx][ty])){ vis[tx][ty]=true; que.push(make_pair(tx,ty)); } } que.pop(); } } int main(){ cin>>n>>m; for(int i=0;i<n;i++){ cin>>mp[i]; } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(is_shuzi(mp[i][j])&&!vis[i][j]){ bfs(i,j); ans++; } } } cout<<ans<<endl; return 0; }