USACO 2025 January Contest Bronze Division - Astral Superposition

Problem link: here

Video link: here

Solution Author: Stefan Dascalescu

Problem Solution

First, if $a$ and $b$ are 0, counting the $G$ and $B$ is enough.

Otherwise, it's a matter of casework as we only care about how does the current value behave with respect to its immediate surroundings.

If we have a B, we must make sure the square situated $a$ to the left and $b$ above is also colored, together with the current square. Otherwise, it's a $-1$ as the grid would be impossible.

If we have a G, then we need to check whether the square situated $a$ to the right and $b below must be colored in both cases, otherwise it depends on whether we have any restriction from the square above.

If we have a W, we don't do anything as the other cases are checked by default.

At the end, we only count the number of squares we colored and this is our answer.

Source codes

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

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    swap(a, b);

    vector<vector<int>> coding(n+1, vector<int> (n+1));
    vector<vector<int>> old_grid(n+1, vector<int> (n+1));

    int total = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            char c;
            cin >> c;

            if (c == 'B') {
                coding[i][j] = 2;
                total++;
            }
            if (c == 'G') {
                coding[i][j] = 1;
                total++;
            }
        }
    }

    if (a == 0 && b == 0) {
        cout << total << '\n';
        return;
    }

    bool bad = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (coding[i][j] == 2) {
                if (i - a <= 0 || j - b <= 0) {
                    bad = 1;
                }
                else {
                    if (old_grid[i - a][j - b] == 0) {
                        bad = 1;
                    }
                    old_grid[i][j] = 1;
                }
            }
            if (coding[i][j] == 1) {
                if (i + a <= n && j + b <= n && coding[i + a][j + b] == 2) {
                    old_grid[i][j] = 1;
                }
                else {
                    if (i - a > 0 && j - b > 0 && old_grid[i - a][j - b] == 1) ;
                    else {
                        old_grid[i][j] = 1;
                    }
                }
            }
        }
    }

    if (bad == 1) {
        cout << -1 << '\n';
    }
    else {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                ans += old_grid[i][j];
            }
        }

        cout << ans << '\n';
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }
    return 0;
}

t = int(input())

for _ in range(t):
    n, a, b = map(int, input().split())
    a, b = b, a

    coding = [[0] * (n + 1) for _ in range(n + 1)]
    old_grid = [[0] * (n + 1) for _ in range(n + 1)]

    total = 0
    for i in range(1, n + 1):
        row = input().strip()
        for j in range(1, n + 1):
            c = row[j - 1]
            if c == 'B':
                coding[i][j] = 2
                total += 1
            elif c == 'G':
                coding[i][j] = 1
                total += 1

    if a == 0 and b == 0:
        print(total)
    else:
        bad = False
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if coding[i][j] == 2:
                    if i - a <= 0 or j - b <= 0:
                        bad = True
                    else:
                        if old_grid[i - a][j - b] == 0:
                            bad = True
                        old_grid[i][j] = 1
                if coding[i][j] == 1:
                    if i + a <= n and j + b <= n and coding[i + a][j + b] == 2:
                        old_grid[i][j] = 1
                    else:
                        if not (i - a > 0 and j - b > 0 and old_grid[i - a][j - b] == 1):
                            old_grid[i][j] = 1

        if bad:
            print(-1)
        else:
            ans = sum(sum(row) for row in old_grid)
            print(ans)