top1编程
← 返回题目
题解

【入门】有多少细胞

1 条题解

  • 0
    @ 2026-7-29 0:18:12
    #include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    
    // 四个方向:上下左右
    const int dx[] = {-1, 1, 0, 0};
    const int dy[] = {0, 0, -1, 1};
    
    void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
        int m = grid.size();
        int n = grid[0].size();
        
        // 边界检查:超出范围、已访问、是0则返回
        if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y] || grid[x][y] == 0) {
            return;
        }
        
        visited[x][y] = true; // 标记为已访问
        
        // 遍历四个方向
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            dfs(grid, visited, nx, ny);
        }
    }
    
    int main() {
        int m, n;
        cin >> m >> n;
        cin.ignore(); // 忽略换行符,避免影响后续getline
        
        vector<vector<int>> grid(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            string line;
            getline(cin, line);
            for (int j = 0; j < n; ++j) {
                grid[i][j] = line[j] - '0'; // 字符转整数
            }
        }
        
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        int count = 0;
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // 找到未访问的非0数字,启动DFS
                if (!visited[i][j] && grid[i][j] != 0) {
                    count++;
                    dfs(grid, visited, i, j);
                }
            }
        }
        
        cout << count << endl;
        return 0;
    }
    
    • 1