题解：P9939 [USACO21OPEN] Acowdemia III B

· · 题解

题目传送门

贪心解决。

为什么？

当两头与同一个草地相邻的牛交朋友的时候，对答案的贡献是 1，而这个草地有两种情况：连接着不同的牛和只连接了这两头牛，这两种情况对答案的多出贡献分别是 1 和 0，由此可见，按照贪心的思想（找到所有与相邻的未使用草地，连接的两头牛交朋友），是可以找到正确答案的。

去除重复

对于草地，我们很容易就可以判断使用与否，用一个二维数组标记一下就可以了。

但是对于牛，不可能开一个四维数组来记录是否交友。

那怎么办？

其实可以不用管。只要按照行和列的顺序依次找每头牛的位置，比如在第 i 行第 j 列的位置有一头牛，这头牛在之前的所有第 x 行第 y 列（x<i,y<j）没有被找到过，也就没有和任何牛交过朋友，那么这头牛交的朋友就不会重复算。

不会算重

对于第 i 行第 j 列的牛，我们先只计算他与第 x 行第 y 列（x<i,y<j）的牛交朋友的交友数量，没有被找到的牛就不会受到影响。

不会漏算

不妨假设第 i 行第 j 列的牛可以和第 r 行第 c 列（r>i,c>j）的牛交朋友。

显而易见，第 r 行第 c 列的牛也一定能与它交朋友，这两头牛之间的交友贡献虽然在遍历到第 i 行第 j 列的牛时不会计算，但是在第 r 行第 c 列时就会计入总量了。

总结

所以，对于一头牛，我们需要找如下的草坪与牛是否能与其交友。

图片解释：已经被找到的牛（黄色），草坪（绿色），当前的牛（红色）。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=3e3+5;
int n,m,k;
int T;
char c[M][M];
int vis[M][M];
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c[i][j];
        }
    }
    int ans=0;
    for(int x=1;x<=n;x++){
        for(int y=1;y<=m;y++){
            if(c[x][y]=='C'){
                int vvs[10]={};
                if(x-1>=1&&c[x-1][y]=='G'&&!vis[x-1][y]){//上边的草地 
                    if(x-2>=1&&c[x-2][y]=='C')ans++,vis[x-1][y]=1;
                    else if(y-1>=1&&c[x-1][y-1]=='C')ans++,vis[x-1][y]=1,vvs[2]=1;
                    else if(y+1<=m&&c[x-1][y+1]=='C')ans++,vis[x-1][y]=1,vvs[3]=1;
                }
                if(y-1>=1&&c[x][y-1]=='G'&&!vis[x][y-1]){//左边的草地 
                    if(x-1>=1&&c[x-1][y-1]=='C'&&!vvs[2])ans++,vvs[2]=1,vis[x][y-1]=1;
                    else if(y-2>=1&&c[x][y-2]=='C')ans++,vis[x][y-1]=1;
                }
                if(y+1<=m&&c[x][y+1]=='G'&&!vis[x][y+1]){//右边的草地 
                    if(x-1>=1&&c[x-1][y+1]=='C'&&!vvs[3])ans++,vis[x][y+1]=1,vvs[3]=1;
                }
            }
        }
    }
    cout<<ans;
}