1 solutions

  • 0
    @ 2022-3-28 18:57:20

    1、通过一个连通‘#’区域内 x 的最大值与最小值,确定矩阵的一条边长,连通‘#’区域内 y 的最大值与最小值确定矩阵的另一条边长。 2、两边相乘就可以得到连通‘#’的最大矩阵。 3、最后再判断一下,连通的‘#’的数量是否等于矩阵的大小,等于为谷仓,否则为奶牛。

    #include <stdio.h>
    #include <math.h>
    #include <algorithm>
    #include <iostream>
    #include <string.h>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <vector>
    using namespace std;
    #define ll long long
    int n,m,mix,miy,mas,may,cow,farm,temp;
    char a[100][100];
    int vis[100][100];
    int dx[4]= {0,0,1,-1},dy[4]= {1,-1,0,0};
    void dfs(int x,int y) {
        vis[x][y]=1;
        temp++;
        mix=min(mix,x);
        miy=min(miy,y);
        mas=max(mas,x);
        may=max(may,y);
        for(int i=0; i<4; i++) {
            int tx=x+dx[i],ty=y+dy[i];
            if(tx>=0&&ty>=0&&tx<n&&ty<m&&!vis[tx][ty]&&a[tx][ty]=='#') {
                dfs(tx,ty);
            }
        }
    }
    int main() {
        scanf("%d%d",&n,&m);
        for(int i=0; i<n; i++) {
            scanf("%s",&a[i]);
        }
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                mix=100,miy=100,mas=0,may=0;
                if(!vis[i][j]&&a[i][j]=='#') {
                    temp=0;
                    dfs(i,j);
                    int k=(1+mas-mix)*(1+may-miy);
                    if(k==temp) {
                        farm++;
                    } else {
                        cow++;
                    }
    
                }
            }
        }
        cout<<farm<<endl;
        cout<<cow<<endl;
        return 0;
    }
    

    Information

    ID
    777
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    4
    Tags
    # Submissions
    35
    Accepted
    17
    Uploaded By