1 条题解

  • 0
    @ 2026-1-27 23:02:02
    #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
    上传者