P1451 求细胞数量

时间:2022-08-30 08:08:14

题目描述

一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。(1<=m,n<=100)?

输入输出格式

输入格式:

输入:整数m,n(m行,n列)

矩阵

输出格式:

输出:细胞的个数

这个题主要是用到了搜索的知识

首先我们先来理解一下题意

输入输出样例

输入样例#1: 
4  10
0234500067
1034560500
2045600671
0000000089
输出样例#1:
4
我们来看这个输入样例,会发现它其实是被分成了0和其他数字的一些范围,我们要找的是非0数字的集合的个数,以一个点的上下左右为可连接到的点,我们就能画出这个东西
0234500067
1034560500
2045600671
0000000089

我们可以看到所有的联通块总共有四个,所以细胞数目是4。
题意理解得差不多了,我们来看怎么实现代码,首先,我们把矩阵读入进去
这里有两种读入方式
1.字符数组读入,判的时候需要再开一个bool数组来标记是细胞和不是细胞(也就是0)
2.一个非常神奇的输入方式,
 scanf("%1d", &a[i][j]);
看到这个1d了吗,他其实就是控制输入场宽,来达到一个一个输入的方法,然后吧,因为读进来的是int所以应该是可以直接判真假,也就是说可以不用开bool数组(不过为了保险起见我还是开了一个)
读进来之后,从每一个数字开始判,当读到第一个非0细胞的时候,把其坐标压进队列并且置为0,然后对其上下左右都进行判断,如果符合条件就也压进队列,每一次都把队头弹出,知道一次队列完成
可能光这样讲不是太好理解,那么我们看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
bool b[101][101];
int n, m, a[101][101], ans = 0;
int dx[4] = {-1, 0, 1, 0},
    dy[4] = {0, 1, 0, -1};
inline void qaq(int x, int y)
{
    int hx[1000], hy[1000], head = 1, tail = 1, tx, ty;
    ans++;
    hx[1] = x, hy[1] = y;
    b[x][y] = false;
    for (; head <= tail; ++head)
    {
        for (int i = 0; i <= 3; ++i)
        {
            tx = hx[head] + dx[i],
            ty = hy[head] + dy[i];
            if (tx > 0 && tx <= m && ty > 0 && ty <= n && b[tx][ty])
            {
                tail++;
                hx[tail] = tx,
                hy[tail] = ty;
                b[tx][ty] = false;
            }
        }
    }
}
int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            b[i][j] = true;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
        {
            scanf("%1d", &a[i][j]);
            if (!a[i][j])
                b[i][j] = false;
        }
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            if (b[i][j])
                qaq(i, j);
    printf("%d", ans);
    return 0;
}

当符合条件,进行qaq(),然后按照队列的方式来进行处理,这个题就完事啦~