2025.9.13 曹立
题目内容
一矩形阵列由数字 \(0\) 到 \(9\) 组成，数字 \(1\) 到 \(9\) 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数
输入描述
第一行两个整数代表矩阵大小 \(m\) 和 \(m\)
接下来 \(m\) 行，每行一个长度为 \(n\) 的只含字符 0 到 9 的字符串，代表这个 \(m \times n\) 的矩阵
输出描述
一行一个整数代表细胞个数
输入输出样例
输入
4 10
0234500067
1034560500
2045600671
0000000089
输出
4
C++实现（bfs版）
#include <bits/stdc++.h>
using namespace std;int n, m;
vector<string> grid;
bool visited[105][105];// 上下左右方向
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};void bfs(int x, int y) {queue<pair<int,int>> q;q.push({x, y});visited[x][y] = true;while (!q.empty()) {auto [cx, cy] = q.front();q.pop();for (int i = 0; i < 4; i++) {int nx = cx + dx[i];int ny = cy + dy[i];if (nx >= 0 && nx < n && ny >= 0 && ny < m) {if (!visited[nx][ny] && grid[nx][ny] != '0') {visited[nx][ny] = true;q.push({nx, ny});}}}}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;grid.resize(n);for (int i = 0; i < n; i++) {cin >> grid[i];}int count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] != '0') {count++;bfs(i, j);}}}cout << count << "\n";return 0;
}C++实现（dfs版）
#include <bits/stdc++.h>
using namespace std;int n, m;
vector<string> grid;
bool visited[105][105];// 方向：上下左右
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};void dfs(int x, int y) {visited[x][y] = true;for (int i = 0; i < 4; i++) {int nx = x + dx[i];int ny = y + dy[i];if (nx >= 0 && nx < n && ny >= 0 && ny < m) {if (!visited[nx][ny] && grid[nx][ny] != '0') {dfs(nx, ny);}}}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;grid.resize(n);for (int i = 0; i < n; i++) {cin >> grid[i];}int count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] != '0') {count++;dfs(i, j);}}}cout << count << "\n";return 0;
}