USACO 2021 US Open Contest Bronze Division - Acowdemia III

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We just need to check for each grass square if it has at least two neighbors which are cows.

The biggest problem is that we want to make sure that by pairing up two cows, we don't lose out on the possibility to go for some better option later on. Therefore, we will start by processing line segments and then the L's (for example, an L would be (i-1, j), (i, j), (i, j+1)).

First we consider line and column segments and then we consider the L's. We first consider the L's which contain something on the previous line and then the one which contain things on the next line.

Source codes

The source codes in C++ and Python can be seen below.

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

int n, m, ans = 0;
char grid[1002][1002];


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> grid[i][j];

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(grid[i][j] != 'G')
                continue;
            if(j >= 1 && j + 1 < m && grid[i][j-1] == 'C' && grid[i][j+1] == 'C')
            {
                ans++;
                grid[i][j] = '.';
            }
            else
                if(i >= 1 && i + 1 < n && grid[i-1][j] == 'C' && grid[i+1][j] == 'C')
                {
                    ans++;
                    grid[i][j] = '.';
                }
        }

    set<pair<pair<int, int>, pair<int, int> > >s;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(grid[i][j] != 'G')
                continue;
            if(grid[i][j] == 'G' && i >= 1 && j >= 1 && grid[i-1][j] == 'C' && grid[i][j-1] == 'C')
            {
                if(s.find({{i-1, j},{i, j-1}}) != s.end());
                else
                {
                    ans++;
                    s.insert({{i-1, j},{i, j-1}});
                    grid[i][j] = '.';
                }
            }
            if(grid[i][j] == 'G' && i >= 1 && j + 1 < m && grid[i-1][j] == 'C' && grid[i][j+1] == 'C')
            {
                if(s.find({{i-1, j},{i, j+1}}) != s.end());
                else
                {
                    ans++;
                    s.insert({{i-1, j},{i, j+1}});
                    grid[i][j] = '.';
                }
            }
            if(grid[i][j] == 'G' && i + 1 < n && j >= 1 && grid[i+1][j] == 'C' && grid[i][j-1] == 'C')
            {
                if(s.find({{i, j-1},{i+1, j}}) != s.end());
                else
                {
                    ans++;
                    s.insert({{i, j-1},{i+1, j}});
                    grid[i][j] = '.';
                }
            }
            if(grid[i][j] == 'G' && i + 1 < n && j + 1 < m && grid[i+1][j] == 'C' && grid[i][j+1] == 'C')
            {
                if(s.find({{i, j+1},{i+1, j}}) != s.end());
                else
                {
                    ans++;
                    s.insert({{i, j+1},{i+1, j}});
                    grid[i][j] = '.';
                }
            }
        }
    cout << ans << '\n';
    return 0;
}

n, m = map(int, input().split())
grid = [list(input().strip()) for _ in range(n)]
ans = 0

for i in range(n):
    for j in range(m):
        if grid[i][j] != 'G':
            continue
        if j >= 1 and j + 1 < m and grid[i][j-1] == 'C' and grid[i][j+1] == 'C':
            ans += 1
            grid[i][j] = '.'
        elif i >= 1 and i + 1 < n and grid[i-1][j] == 'C' and grid[i+1][j] == 'C':
            ans += 1
            grid[i][j] = '.'

s = set()
for i in range(n):
    for j in range(m):
        if grid[i][j] != 'G':
            continue
        if grid[i][j] == 'G' and i >= 1 and j >= 1 and grid[i-1][j] == 'C' and grid[i][j-1] == 'C':
            pair_tuple = ((i-1, j), (i, j-1))
            if pair_tuple not in s:
                ans += 1
                s.add(pair_tuple)
                grid[i][j] = '.'
        if grid[i][j] == 'G' and i >= 1 and j + 1 < m and grid[i-1][j] == 'C' and grid[i][j+1] == 'C':
            pair_tuple = ((i-1, j), (i, j+1))
            if pair_tuple not in s:
                ans += 1
                s.add(pair_tuple)
                grid[i][j] = '.'
        if grid[i][j] == 'G' and i + 1 < n and j >= 1 and grid[i+1][j] == 'C' and grid[i][j-1] == 'C':
            pair_tuple = ((i, j-1), (i+1, j))
            if pair_tuple not in s:
                ans += 1
                s.add(pair_tuple)
                grid[i][j] = '.'
        if grid[i][j] == 'G' and i + 1 < n and j + 1 < m and grid[i+1][j] == 'C' and grid[i][j+1] == 'C':
            pair_tuple = ((i, j+1), (i+1, j))
            if pair_tuple not in s:
                ans += 1
                s.add(pair_tuple)
                grid[i][j] = '.'

print(ans)