记录--洛谷 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;
}