自动搬运

查看原文

来自洛谷，原作者为

	sPERbEETLE **

搬运于2025-08-24 22:53:11，当前版本为作者最后更新于2025-08-14 23:13:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

在 $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;
}//完结撒花