1 条题解
-
0
#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
- 上传者