Home » 国际竞赛 » Details

USACO 2021 US Open, Bronze Problem 3. Acowdemia III

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午12:20

USACO 2021 US Open, Bronze Problem 3. Acowdemia III

Bessie is a busy computer science graduate student. However, even graduate students need friends. As a result, Farmer John has opened a pasture with the explicit purpose of helping Bessie and other cows form lasting friendships.

Farmer John's pasture can be regarded as a large 2D grid of square "cells" (picture a huge chess board). Each cell is labeled with:

C if the cell contains a cow.
G if the cell contains grass.
. if the cell contains neither a cow nor grass.

For two distinct cows to become friends, the cows must choose to meet at a grass-covered square that is directly horizontally or vertically adjacent to both of them. During the process, they eat the grass in the grass-covered square, so future pairs of cows cannot use that square as a meeting point. The same cow may become friends with more than one other cow, but no pair of cows may meet and become friends more than once.

Farmer John is hoping that numerous pairs of cows will meet and become friends over time. Please determine the maximum number of new friendships between distinct pairs of cows that can possibly be created by the end of this experience.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $N$ and $M$ ( $N, M \leq 1000$ ).The next $N$ lines each contain a string of $M$ characters, describing the pasture.

OUTPUT FORMAT (print output to the terminal / stdout):

Count the maximum number of pairs of cows that can become friends by the end of the experience.

SAMPLE INPUT:

4 5
.CGGC
.CGCG
CGCG.
.CC.C

SAMPLE OUTPUT:

If we label the cow in row $i$ and column $j$ with coordinates $(i, j)$ , then in this example there are cows at $(1, 2)$ , $(1, 5)$ , $(2, 2)$ , $(2, 4)$ , $(3, 1)$ , $(3, 3)$ , $(4, 2)$ , $(4, 3)$ , and $(4, 5)$ . One way for four pairs of cows to become friends is as follows:

The cows at $(2, 2)$ and $(3, 3)$ eat the grass at $(3, 2)$ .
The cows at $(2, 2)$ and $(2, 4)$ eat the grass at $(2, 3)$ .
The cows at $(2, 4)$ and $(3, 3)$ eat the grass at $(3, 4)$ .
The cows at $(2, 4)$ and $(1, 5)$ eat the grass at $(2, 5)$ .

SCORING:

Test cases 2-4 satisfy $N = 2$ .
Test cases 5-12 satisfy no additional constraints.

Problem credits: Benjamin Qi

USACO 2021 US Open, Bronze Problem 3. Acowdemia III 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

There's a simple greedy strategy. Iterate over each grass square.

If it is adjacent to at most one cow, then nothing happens.
If it is adjacent to greater than two cows, then it is adjacent to two cows on opposite sides. Increment the answer by one.
Otherwise if exactly 2 adjacent cows we pair those up. That is, insert this pair of cows into a set.

At the end, we add the number of distinct pairs in the set to the answer.

My code:

#include<bits/stdc++.h>
using namespace std;

int main() {
	int N,M; cin >> N >> M;
	vector<string> G(N); for (string& row: G) cin >> row;
	auto exists_cow = [&](int i, int j) { 
		return 0 <= i && i < N && 0 <= j && j < M && G[i][j] == 'C';
	};
	set<vector<pair<int,int>>> pairs;
	int ans = 0;
	for (int i = 0; i < N; ++i) 
		for (int j = 0; j < M; ++j) if (G[i][j] == 'G') {
			vector<pair<int,int>> v;
			int dx[]{1,0,-1,0};
			int dy[]{0,1,0,-1};
			for (int d = 0; d < 4; ++d) {
				int ii = i+dx[d], jj = j+dy[d];
				if (exists_cow(ii,jj)) v.emplace_back(ii,jj);
			}
			if (v.size() > 2) {
				++ans;
				continue;
			}
			if (v.size() == 2) {
				sort(begin(v),end(v));
				pairs.insert(v);
			}
		}
	cout << pairs.size()+ans << "\n";
}

Danny Mittal's code (similar greedy strategy, but doesn't use a set):

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class AcowdemiaIII {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int m = Integer.parseInt(tokenizer.nextToken());
        char[][] pasture = new char[n + 2][];
        pasture[0] = new char[m + 2];
        Arrays.fill(pasture[0], '.');
        pasture[n + 1] = pasture[0];
        for (int y = 1; y <= n; y++) {
            pasture[y] = ('.' + in.readLine() + '.').toCharArray();
        }
        int answer = 0;
        for (int y = 1; y <= n; y++) {
            for (int x = 1; x <= m; x++) {
                if (pasture[y][x] == 'G' && ((pasture[y][x - 1] == 'C' && pasture[y][x + 1] == 'C') || (pasture[y - 1][x] == 'C' && pasture[y + 1][x] == 'C'))) {
                    pasture[y][x] = '.';
                    answer++;
                }
            }
        }
        for (int y = 1; y <= n; y++) {
            for (int x = 1; x <= m; x++) {
                if (pasture[y][x] == 'C') {
                    if (pasture[y + 1][x - 1] == 'C') {
                        if (pasture[y][x - 1] == 'G') {
                            pasture[y][x - 1] = '.';
                            answer++;
                        } else if (pasture[y + 1][x] == 'G') {
                            pasture[y + 1][x] = '.';
                            answer++;
                        }
                    }
                    if (pasture[y + 1][x + 1] == 'C') {
                        if (pasture[y][x + 1] == 'G') {
                            pasture[y][x + 1] = '.';
                            answer++;
                        } else if (pasture[y + 1][x] == 'G') {
                            pasture[y + 1][x] = '.';
                            answer++;
                        }
                    }
                }
            }
        }
        System.out.println(answer);
    }
}

[/hide]