本文共 2098 字，大约阅读时间需要 6 分钟。

为了解决这个问题，我们需要计算给定矩阵中的细胞个数。细胞由数字1到9组成，相邻的数字（上下左右）属于同一个细胞。我们可以使用广度优先搜索（BFS）来遍历矩阵，标记访问过的细胞，避免重复计算。

方法思路

解决代码

#include 
   
    
#include 
    
     
#include 
     
      
using namespace std;
int m, n;
int jz[1001][1001];
bool visited[1001][1001];
int sum = 0;
queue
      
       
        > q;
void input() {
    cin >> m >> n;
    for (int i = 1; i <= m; ++i) {
        string s;
        cin >> s;
        for (int j = 1; j <= n; ++j) {
            jz[i][j] = s[j-1] - '0';
            if (jz[i][j] != 0) {
                visited[i][j] = false;
            } else {
                visited[i][j] = false;
            }
        }
    }
}
void bfs(int i, int j) {
    if (i < 1 || i > m || j < 1 || j > n) {
        return;
    }
    if (jz[i][j] != 1) {
        return;
    }
    if (visited[i][j]) {
        return;
    }
    visited[i][j] = true;
    q.push({i, j});
    sum++;
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    while (!q.empty()) {
        auto current = q.front();
        q.pop();
        int x = current.first;
        int y = current.second;
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx >= 1 && nx <= m && ny >= 1 && ny <= n) {
                if (jz[nx][ny] == 1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
    }
}
int main() {
    input();
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (jz[i][j] == 1 && !visited[i][j]) {
                bfs(i, j);
            }
        }
    }
    cout << sum << endl;
    return 0;
}
       
      
     
    
   

代码解释

该方法使用BFS高效地遍历矩阵，确保每个单元格只被访问一次，时间复杂度为O(mn)，适用于较大的矩阵。

转载地址：http://inrfk.baihongyu.com/