一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如: 阵列 4 10 0234500067 1034560500 2045600671 0000000089 有4个细胞C++语言实现
时间: 2023-06-14 15:03:55 浏览: 55
以下是C++语言实现的代码:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100; // 最大矩形阵列大小
int n, m; // 矩形阵列大小
int a[MAXN][MAXN]; // 矩形阵列
bool vis[MAXN][MAXN]; // 是否访问过
int dx[] = {0, 0, 1, -1}; // 上下左右四个方向的偏移量
int dy[] = {1, -1, 0, 0};
void dfs(int x, int y, int color) { // 深度优先搜索
vis[x][y] = true; // 标记已访问
a[x][y] = color; // 并将该细胞的值设为color
for (int i = 0; i < 4; i++) { // 四个方向搜索
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue; // 越界
if (a[nx][ny] == 0) continue; // 不是细胞
if (vis[nx][ny]) continue; // 已访问
dfs(nx, ny, color); // 继续搜索
}
}
int main() {
cin >> n >> m;
memset(vis, false, sizeof(vis)); // 初始化为未访问
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
int color = 1; // 细胞颜色从1开始编号
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] != 0 && !vis[i][j]) { // 未访问过的细胞
dfs(i, j, color); // 深度优先搜索
color++; // 细胞颜色加1
}
}
}
cout << color - 1 << endl; // 细胞个数为颜色数减1
return 0;
}
```
输入格式:
第一行包含两个正整数n和m,表示矩形阵列的行数和列数。
接下来n行,每行m个数字,表示矩形阵列的元素。
输出格式:
一个整数,表示矩形阵列中的细胞个数。
输入样例:
```
4 10
0234500067
1034560500
2045600671
0000000089
```
输出样例:
```
4
```