求细胞数量
题目描述:一矩形阵列由数字 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;
}
}广搜的一道水题。
