题解：P9939 [USACO21OPEN] Acowdemia III B

· · 题解

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

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

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

如果正好有两头牛，用数据结构记录这一对牛，如果重复就不记录，这里我采用的是 unordered_map。

否则，跳过。

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n,m,ans,p;
int x[N][N],vis[N][N];
char c[N][N];
map <int,int> mp[N * N];
void update(int ax,int ay,int bx,int by,int cx,int cy) {
    if(!mp[x[ax][ay]][x[bx][by]] && c[ax][ay] == 'C' && c[bx][by] == 'C' && c[cx][cy] == 'G' && !vis[cx][cy]) mp[x[ax][ay]][x[bx][by]] = 1,vis[cx][cy] = 1,ans++;
}
int main() {
    cin >> n >> m;
    for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) cin >> c[i][j],x[i][j] = ++p;
    for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) update(i,j,i,j + 2,i,j + 1);
    for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) update(i,j,i + 2,j,i + 1,j);
    for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) update(i,j,i + 1,j + 1,i,j + 1);
    for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) update(i,j,i + 1,j + 1,i + 1,j);
    for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) update(i,j,i - 1,j + 1,i,j + 1);
    for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) update(i + 1,j,i,j + 1,i,j);
    cout << ans;
    return 0;
}