求细胞数量

作者: qiqi 分类: 经典案例 发布时间: 2025-10-14 20:11

提交链接

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

#include <bits/stdc++.h>
using namespace std;
char maze[110][110];
bool v[110][110];

int fx[] = {0, 1, 0, -1}; //右下左上
int fy[] = {1, 0, -1, 0};
struct node
{
	int i, j; //格子的行和列
};
int n, m, cnt = 0;

void bfs(int x, int y);

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> maze[i];

	for (int i = 0; i < n; i++)

	{
		for (int j = 0; j < m; j++)

		{
			if ( maze[i][j] != '0' && !v[i][j])
			{
				cnt++;
				bfs(i, j);
				cout << i << ' ' << j << endl;
			}
		}
	}

	cout << cnt << endl;

	return 0;
}

void bfs(int x, int y)
{
	//相邻的格子都踩一遍
	queue<node> q;
	q.push({x, y});
	v[x][y] = true;

	while (!q.empty())
	{
		node t1 = q.front();
		for (int i = 0; i < 4; i++) //4个方向
		{
			int dx = t1.i + fx[i];
			int dy = t1.j + fy[i];

			if (v[dx][dy] == true)
				continue;
			if (dx < 0 || dx >= n || dy < 0 || dy >= m)
				continue;
			if (maze[dx][dy] == '0')
				continue;

			q.push({dx, dy});

		}
		node t = q.front();
		q.pop();
		v[t.i][t.j] = true;

	}

}

广搜的一道水题。

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

标签云