1 条题解
-
0
#include <bits/stdc++.h> using namespace std; int n,m; char crr[110][110]; // 存储地图,#为障碍物/谷仓,.为空地 int flag[110][110]={};// 访问标记,1=已访问,0=未访问 int dx[4]={0,1,0,-1}; // 方向偏移量:右→下→左→上 int dy[4]={1,0,-1,0}; int max_x,max_y,min_x,min_y; // 存储单个连通块的最大/最小行列边界 // DFS:遍历#连通块,更新其边界范围,标记所有节点为已访问 void dfs(int x,int y){ for(int i=0;i<4;i++){ int tx=x+dx[i]; int ty=y+dy[i]; // 先判断坐标合法性:在地图内+未访问+是# if(tx>=1 && tx<=n && ty>=1 && ty<=m && flag[tx][ty]==0 && crr[tx][ty]=='#'){ flag[tx][ty]=1; // 标记为已访问,避免重复遍历 // 更新当前连通块的边界 max_x=max(max_x,tx); max_y=max(max_y,ty); min_x=min(min_x,tx); min_y=min(min_y,ty); dfs(tx,ty); // 递归遍历下一个节点 } } } // 评估函数:判断[min_x,max_x]行、[min_y,max_y]列的矩形是否全为# bool assess(int a,int b,int c,int d){ for(int i=a;i<=b;i++){ for(int j=c;j<=d;j++){ if(crr[i][j] == '.') return false; // 存在空地,不是完整矩形 } } return true; // 全为#,是完整矩形(谷仓) } int main(){ cin>>n>>m; // 读入n行m列地图(坐标从1开始,符合题目习惯) for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>crr[i][j]; } } int sum=0,sum2=0; // sum=谷仓数(完整矩形),sum2=奶牛数(非矩形) // 遍历所有地图节点,寻找未访问的#起点 for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ // 找到有效起点:是# + 未被访问 if(crr[i][j]=='#' && flag[i][j]==0){ // 修复:初始化当前连通块的边界为起点坐标 max_x = min_x = i; max_y = min_y = j; flag[i][j] = 1; // 修复:标记起点为已访问 dfs(i,j); // 修复:调用DFS,遍历整个连通块并更新边界 // 修复:获取有效边界后,再判断是否为完整矩形 if(assess(min_x,max_x,min_y,max_y)){ sum++; // 是完整矩形,谷仓数+1 }else{ sum2++; // 非完整矩形,奶牛数+1 } } } } // 输出结果:先谷仓数,再奶牛数 cout<<sum<<endl<<sum2; return 0; }
信息
- ID
- 1293
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者