P9939 [USACO21OPEN] Acowdemia III B 题解

这是一道 USACO 铜组的数据结构黄题。

1. 题目不难理解，就是问在一片草地中，找出一共有多少对牛往上下左右四个方向走，能吃到同一棵草。

2. 总体思路就是先找到一棵草，看上下左右有没有牛。

3. 如果有多于两只牛，肯定能成为一对。

4. 如果正好有两头牛，用数据结构记录这一对牛，如果重复就不记录。

5. 否则，跳过。

思路在 C + + 代码里。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ull unsigned long long
int mp[1005][1005],n,m,ans;    //地图。
map<vector<pii>,int> v;    //用来存储一对一对的奶牛。
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    memset(mp,-1,sizeof(mp));    //初始状态不为草也不为奶牛。
    //输入。
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
		{
            char ch;
            cin>>ch;
            if(ch=='G') mp[i][j]=0; //当前变量为草。
            if(ch=='C') mp[i][j]=1; //当前变量为牛。
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(!mp[i][j])    //当前变量为草。
			{
                int cnt=0;    //草附近有多少奶牛。
                vector<pii> c;
                if(i+1<=n&&mp[i+1][j]==1)   //往下看。
				{
					cnt++;
					c.push_back({i+1,j});
				}
                if(j+1<=m&&mp[i][j+1]==1)   //往右看。
				{
					cnt++;
					c.push_back({i,j+1});
				}
                if(i-1>=1&&mp[i-1][j]==1)   //往上看。
				{
					cnt++;
					c.push_back({i-1,j});
				}
                if(j-1>=1&&mp[i][j-1]==1)   //往左看。
				{
					cnt++;
					c.push_back({i,j-1});
				}
                if(cnt>2) ans++; // 当旁边有多于两头牛。
				else if(cnt==2) // 当旁边正好有两头牛。
				{
                    sort(c.begin(),c.end());
                    v[c]++; //记录每对奶牛。
                }
            }
    cout<<ans+v.size(); // 旁边多于两只牛的草的个数加一共有多少对牛。
    return 0;
}