1 条题解
-
0
#include <bits/stdc++.h> using namespace std; // [1] arr数组-存储数字矩阵,字符类型,0表示非细胞,1-9表示细胞,'-'表示已访问的细胞(避免重复计数) char arr[200][200]; // [2] n-矩阵的行数;m-矩阵的列数(0-based坐标) int n,m; // [3] 四个方向偏移量(下、右、上、左),用于遍历当前细胞的上下左右相邻位置 int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; // [4] DFS递归函数:遍历并标记当前细胞所在的连通区域,将所有连通的细胞标记为'-'(已访问) // 参数说明:x-当前细胞的横坐标;y-当前细胞的纵坐标 void dfs(int x,int y){ // [5] 递归终止条件:当前位置是0(非细胞)或已标记为'-'(已访问),直接返回 if(arr[x][y]=='0' || arr[x][y]=='-'){ return ; } // [6] 标记当前细胞为已访问(避免后续重复计数) arr[x][y]='-'; // [7] 遍历四个方向,扩展当前细胞的连通区域 for(int i=0;i<4;i++){ // [8] 计算相邻位置的横坐标和纵坐标 int tx=x+dx[i]; int ty=y+dy[i]; // [9] 合法性判断:相邻位置在矩阵范围内,且是未访问的细胞(1-9) if(tx>=0 && tx<n && ty>=0 && ty<m && (arr[tx][ty]>='1' && arr[tx][ty]<='9')){ // [10] 递归遍历相邻的细胞 dfs(tx,ty); } } } int main(){ // [11] 读取矩阵的行数n和列数m cin>>n>>m; // [12] 遍历矩阵,读取每个位置的数字字符 for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>arr[i][j]; } } // [13] sum-统计细胞的总个数,初始化为0 int sum=0; // [14] 遍历矩阵的每个位置,寻找未访问的细胞(1-9) for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ // [15] 找到未访问的细胞,细胞计数+1 if(arr[i][j]>='1' && arr[i][j]<='9'){ sum++; // [16] 调用DFS标记该细胞所在的整个连通区域为已访问 dfs(i,j); } } } // [17] 输出细胞的总个数 cout<<sum; return 0; }
- 1
信息
- ID
- 1296
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者