1 条题解

  • 0
    @ 2026-2-4 20:00:17
    #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
    上传者