题解：P9939 [USACO21OPEN] Acowdemia III B

· · 题解

题目大意

在 N \times M 的矩形里，每一格有三种情况：

  1. C 表示这个格子有一个奶牛。
  2. G 表示这个格子有一片草。
  3. . 表示这个格子什么也没有。

两头奶牛都水平或竖直的相邻的格子里有草，就可以成为一对朋友（一头奶牛可以与多头其他奶牛成为朋友，但是同一对奶牛不能见面并成为朋友多于一次）。

输出的是最大的朋友对数。

做法：贪心+分类讨论

我们可以先枚举每一个格子，如果是奶牛所在格，我们就往下判。\ 我们可以将其分为八种情况，但是为了不重复我们只判其中四种在他后面和下面的格子。 如图：

（3 和 4 可以把 G 和 . 交换哦！）

但在判 3 和 4 一定要搞懂顺序，为什么这么说呢？是因为你在判两个位置的时候他可能会公用一个 i + 1, j 的位置，所以如果在 3 情况时两个位置都是G，你选了 i + 1, j 位置但 4 情况下面没有草时，显然并不是更优。所以一定要调整好顺序，保证最优性。

下面是ACcode

#include <bits/stdc++.h>
#define IAKIOI ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define re read()
#define wr(n) write(n)
#define endl '\n'
#define sp putchar(' ')

const int N = 1e6 + 10, M = 1e3 + 10;

using namespace std;

inline int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (isdigit(c)) {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}

inline void write(int x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int n, m;
char a[M][M];

int main() {
//  freopen("friend.in", "r", stdin);
//  freopen("friend.out", "w", stdout);
    IAKIOI //ios
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j]; //输入
    int ans = 0;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        if (a[i][j] != 'C') continue; //判断是否是奶牛所在格
        if (i + 2 <= n && a[i + 1][j] == 'G' && a[i + 2][j] == 'C') ans++, a[i + 1][j] = '.'; //正下方
        if (j + 2 <= m && a[i][j + 1] == 'G' && a[i][j + 2] == 'C') ans++, a[i][j + 1] = '.'; //正右方
        if (i + 1 <= n && j + 1 <= m && (a[i + 1][j] == 'G' || a[i][j + 1] == 'G') && a[i + 1][j + 1] == 'C') { //右下方
            ans++;
            if (a[i][j + 1] == 'G') a[i][j + 1] = '.'; //记得不要写反了
            else a[i + 1][j] = '.';
        }
        if (i + 1 <= n && j - 1 >= 1 && (a[i + 1][j] == 'G' || a[i][j - 1] == 'G') && a[i + 1][j - 1] == 'C') { //左下方
            ans++;
            if (a[i][j - 1] == 'G') a[i][j - 1] = '.'; //同上上哦
            else a[i + 1][j] = '.';
        }
    }
    cout << ans << endl;
    return 0;
}//完结撒花