记录--洛谷 P1451 求细胞数量

如果想查看完整题目，请前往洛谷 P1451 求细胞数量

P1451 求细胞数量

题目描述

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

输入格式

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

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

输出格式

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

思路

一坨细胞在一起只算一个，所以要求的细胞数是方阵中有几个一坨。
bfs将聚在一起的细胞标记。

C++完整代码

#include<bits/stdc++.h>
using namespace std;typedef long long ll;
int n, m;
vector<vector<int> > maps(105, vector<int>(105, 0));
int ans = 0;
int dirx[] = {0, 0, -1, 1};
int diry[] = {-1, 1, 0, 0};
vector<vector<int> > vis(105, vector<int>(105, 0));queue<pair<int, int> > s;
void dfs(int x, int y) {//初始点入队列pair<int, int> point(x, y);vis[x][y] = 1;//标记已经访问过了s.push(point);//如果队列空了，说明这个初始点周围所有的1~9都已经标记过了，这一坨就算1个细胞了。while(!s.empty()) {int tx = s.front().first;int ty = s.front().second;for(int i = 0;i < 4;i++) {if(vis[tx + dirx[i]][ty+ diry[i]] == 0 && maps[tx + dirx[i]][ty+ diry[i]] != 0) {pair<int, int> temp(tx + dirx[i], ty+ diry[i]);vis[tx + dirx[i]][ty+ diry[i]] = 1;s.push(temp);}}s.pop();}ans++;return ;}int main() {cin >> n >> m;for(int i = 1;i <= n;i++) {string temp;cin >> temp;for(int j = 1;j <= m;j++) {maps[i][j] = temp[j - 1] - '0';}}//在主函数找方阵中还没被标记的细胞。for(int i = 1;i <= n;i++) {for(int j = 1;j <= m;j++ ) {if(vis[i][j] == 0 && maps[i][j] != 0) {dfs(i, j);}}}cout << ans << endl;return 0;
}