题解：P9939 [USACO21OPEN] Acowdemia III B

· · 题解

前言

才知道，这题可以写题解，这题都做过好久了。同样的老师，自然同样的思路。

前置知识

分类讨论和贪心。

思路

这题显然可以进行分类讨论。

  1. 若两头奶牛在同一条直线上，且只间隔着一块草地，则它们可以见面。分为横竖，其实都一样。
  2. 若两头奶牛及一块草地呈现拐角状，也能够见面。比如 2 \times 2 的 C.GC。一共四种。

既然可以搭配了，那么还要处理一些条件哦。

  1. 一个见面位置最多只能供一组奶牛使用，即不能出现两组奶牛选择同一个位置作为见面地点。不可以重读使用哦。
  2. 一头奶牛可以和其他不同的奶牛在不同的位置见面。

    代码

    #include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N=1005;
char op;
int n,m,ans;
int a[N][N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cin>>op;
        a[i][j]=(op=='C'?1:(op=='G'?2:0));
    }
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(a[i][j]==2){
            if(a[i-1][j]==1&&a[i+1][j]==1||a[i][j-1]==1&&a[i][j+1]==1){
                a[i][j]=0;
                ans++;
            }
        }
    }
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(a[i][j]==1&&a[i+1][j-1]==1){
            if(a[i][j-1]==2){
                a[i][j-1]=0;
                ans++;
            }
            else if(a[i+1][j]==2){
                a[i+1][j]=0;
                ans++;
            }
        }
        if(a[i][j]==1&&a[i+1][j+1]==1){
            if(a[i][j+1]==2){
                a[i][j+1]=0;
                ans++;
            }
            else if(a[i+1][j]==2){
                a[i+1][j]=0;
                ans++;
            }
        }
    } 
}
cout<<ans;
return 0;
}