题解：P9939 [USACO21OPEN] Acowdemia III B

题目分析

我们枚举每一块草坪，并且要求两头牛来到这里交朋友。为了使答案最大，我们每一次取的两头牛都尽量不要和后面的选择重复。那么，我们针对草坪周围牛的数量，可以分出以下情况：

如果这块草坪周围有两头牛成一条直线时，我们选这两头牛显然不会和后面的选择重复。所以，我们可以直接让答案加 $1$ 。
否则，就有可能出现下面的情况：

因此，我们需要先把这对牛保存下来，后面再去重，然后统计答案。

code

CPP

#include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
#define fr first
#define sc second
#define pq priority_queue
#define gr greater<int>
using ll=long long;
using db=double;
using i128=__int128;
using pii=pair<int,int>;

int n,m,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
string a[1005];

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]=' '+a[i];
    }

    set<pii>st;
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='G'){
                vector<int>vec;
                for(int k=0;k<4;k++){
                    int x=i+dx[k],y=j+dy[k];
                    if(x<1||x>n||y<1||y>m) continue;
                    if(a[x][y]=='C') vec.push_back((x-1)*m+y);
                }
                if(vec.size()<2) continue;
                if(vec.size()==2){
                    int mi=min(vec[0],vec[1]),ma=max(vec[0],vec[1]);
                    st.insert({mi,ma});
                }
                else ans++;
            }
        }
    }
    ans+=st.size();

    cout<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--) solve();
    return 0;
}

题解：P9939 [USACO21OPEN] Acowdemia III B

文章操作

题目分析

code

相关推荐

评论

题解：P9939 [USACO21OPEN] Acowdemia III B