1 条题解

  • 0
    @ 2026-1-28 10:16:44
    #include <bits/stdc++.h>
    using namespace std;
    
    // [1] arr数组-存储牧场状态:0=草地(.,无草丛)、1=草丛(#,未访问)、2=草丛(#,已访问,避免重复计数)
    int arr[200][200];
    // [2] 四个方向偏移量(右、下、左、上),用于遍历当前草丛的上下左右相邻位置
    int dx[4]={0,1,0,-1};
    int dy[4]={1,0,-1,0};
    // [3] n-牧场的行数(输入的R);m-牧场的列数(输入的C)
    int n,m;
    
    // [4] DFS递归函数:遍历并标记当前草丛所在的连通区域,将所有连通的草丛标记为已访问(2)
    // 参数说明:x-当前草丛的横坐标(行号);y-当前草丛的纵坐标(列号)
    void dfs(int x,int y){
        // [5] 递归终止条件:当前位置是草地(0)或已访问的草丛(2),直接返回
    	if(arr[x][y]==0 || arr[x][y]==2) return;
        // [6] 标记当前草丛为已访问(2),避免后续重复计数
    	arr[x][y]=2;
        // [7] 遍历四个方向,扩展当前草丛的连通区域
    	for(int i=0;i<4;i++){
            // [8] 计算相邻位置的横坐标和纵坐标
    		int tx=x+dx[i];
    		int ty=y+dy[i];
            // [9] 合法性判断:相邻位置在牧场范围内,且是未访问的草丛(1)
    		if(tx>=0 && tx<n && ty>=0 && ty<m && arr[tx][ty]==1){
                // [10] 递归遍历相邻的草丛
    			dfs(tx,ty);
    		}	
    	}
    }
    
    int main(){
        // [11] 读取牧场的行数n(R)和列数m(C)
    	cin>>n>>m;
    	char c;
        // [12] 遍历牧场,读取每个位置的字符并转换为状态值
    	for(int i=0;i<n;i++){
    		for(int j=0;j<m;j++){
    			cin>>c;
    			if(c=='.'){
                    // [13] 草地(.),状态设为0
    				arr[i][j]=0;
    			}else{
                    // [14] 草丛(#),状态设为1(未访问)
    				arr[i][j]=1;
    			}
    		}
    	}
        // [15] sum-统计草丛的总个数,初始化为0
    	int sum=0;
        // [16] 遍历牧场的每个位置,寻找未访问的草丛(1)
    	for(int i=0;i<n;i++){
    		for(int j=0;j<m;j++){
                // [17] 找到未访问的草丛,计数+1
    			if(arr[i][j]==1){
    				sum++;
                    // [18] 调用DFS标记该草丛所在的整个连通区域为已访问
    				dfs(i,j);
    			}
    		}
    	}
        // [19] 输出草丛的总个数
    	cout<<sum;
    	return 0;
    }
    
    • 1

    信息

    ID
    1289
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者