USACO 2023 February Contest Bronze Division - Stamp Grid

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This problem is another example of a task where brute force solutions are good enough to help us pass the test cases, but we need to think at how to get the brute force done properly.

Given that four rotations return us to the original state, it makes a lot of sense to think at relying on each one of them and see which squares can be covered as a result of applying a certain stamp there.

Let's now think at what is the necessary condition for a stamp to be applied on a position - It turns out that we only need to see if all stars from the stamp match with stars on the grid.

Therefore, we can now think at fixing a rotation of the stamp, try every \(K \cdot K\) submatrix and see if after trying everything, all stars have been stamped at least once.

We have small grids, so the time complexity will not be an issue for this problem.

Source codes

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

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;

        vector<string> grid(N);
        for (int i = 0; i < N; ++i) {
            cin >> grid[i];
        }

        int K;
        cin >> K;
        vector<string> stamp(K);
        for (int i = 0; i < K; ++i) {
            cin >> stamp[i];
        }

        vector<vector<char>> ans(N, vector<char>(N, '.'));
        for (int rot = 0; rot < 4; ++rot) {
            for (int i = 0; i <= N - K; ++i)
                for (int j = 0; j <= N - K; ++j) {
                    bool match = true;
                    for (int a = 0; a < K && match; ++a)
                        for (int b = 0; b < K; ++b)
                            if (!(grid[i + a][j + b] == '*' || stamp[a][b] == '.')) {
                                match = false;
                                break;
                            }
                    if (match)
                        for (int a = 0; a < K; ++a)
                            for (int b = 0; b < K; ++b)
                                if (stamp[a][b] == '*') ans[i + a][j + b] = '*';
                }
            vector<string> new_stamp(K, string(K, '.'));
            for (int i = 0; i < K; ++i)
                for (int j = 0; j < K; ++j) {
                    new_stamp[j][K - 1 - i] = stamp[i][j];
                }
            stamp = new_stamp;
        }
        bool isEqual = true;
        for (int i = 0; i < N; ++i)
            if (grid[i] != string(ans[i].begin(), ans[i].end())) {
                isEqual = false;
                break;
            }
        cout << (isEqual ? "YES" : "NO") << '\n';
    }

    return 0;
}

t = int(input())

for _ in range(t):
    s = input()
    n = int(input())

    grid = []
    for i in range(n):
        s = input()
        grid.append(s)

    k = int(input())

    stamp = [[0] * k for _ in range(k)]
    for i in range(k):
        s = input()
        for j in range(k):
            stamp[i][j] = s[j]

    visited = [[0] * n for _ in range(n)]
    for rot in range(4):
        for L in range(n - k + 1):
            for C in range(n - k + 1):
                ok = 1
                for pos in range(k):
                    for pos2 in range(k):
                        if stamp[pos][pos2] == '*' and grid[L + pos][C + pos2] == '.':
                            ok = 0
                if ok == 1:
                    for pos in range(k):
                        for pos2 in range(k):
                            if stamp[pos][pos2] == '*' and grid[L + pos][C + pos2] == '*':
                                visited[L + pos][C + pos2] = 1


        new_stamp = [[0] * k for _ in range(k)]
        for L in range(k):
            for C in range(k):
                new_stamp[C][k - 1 - L] = stamp[L][C];
        stamp = new_stamp

    bad = 0
    for i in range(n):
        for j in range(n):
            if grid[i][j] == '*' and visited[i][j] == 0:
                bad = 1

    if bad == 1:
        print("NO")
    else:
        print("YES")