专栏文章

题解：P9939 [USACO21OPEN] Acowdemia III B

___biu_biu_biu__
P9939题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miocqw04
此快照首次捕获于
2025/12/02 17:04
3 个月前
此快照最后确认于
2025/12/02 17:04
3 个月前
查看原文
题目不难理解，就是问在一片草地中，找出一共有多少对牛往上下左右四个方向走，能吃到同一棵草。
总体思路就是先找到一棵草，看上下左右有没有牛。
如果有多于两只牛，肯定能成为一对。
如果正好有两头牛，用数据结构记录这一对牛，如果重复就不记录，这里我采用的是 unordered_map。
否则，跳过。
CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...