Subtask 1

When $A=B=0$, the answer is simply the number of non-white pixels. Black pixels correspond to the same star appearing in both photos, and gray pixels correspond to a star appearing in the first photo but disappearing from the second.

Subtask 2

Since stars only move within each row, we can solve each row independently. For each row, we can try all $2^N$ possibilities to assign stars to each position within the row, and check whether it is consistent with the output. One way to generate all such possibilities is by using bitmasks. For each possibility, the following conditions must be checked.

1. A black pixel implies that there must be stars at that location as well as the location to the left of it.
2. A white pixel implies there must not be a star at that location.
3. A gray pixel implies that there must be a star at that location or the location to the left of it.

The final step is to output the sum of the minimum answers across rows, or $-1$ if any row is impossible. The runtime per test is $O(N^22^N)$.

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

int solve() {
    int N, A, B;
    cin >> N >> A >> B;
    vector<string> rows(N);
    for (auto &row : rows) cin >> row;
    assert(A == 1 && B == 0);
    int ans = 0;
    for (const auto &row : rows) {
        int row_ans = INT_MAX;
        for (int mask = 0; mask < (1 << N); ++mask) {
            vector<bool> has_star(N);
            bool ok = 1;
            for (int c = 0; c < N; ++c)
                if (mask & (1 << c)) has_star[c] = 1;
            for (int c = 0; c < N; ++c) {
                if (row[c] == 'W') {
                    ok &= !has_star[c];
                } else if (row[c] == 'G') {
                    ok &= has_star[c] || (c && has_star[c - 1]);
                } else {
                    ok &= c && has_star[c] && has_star[c - 1];
                }
            }
            if (ok) {
                row_ans =
                    min(row_ans, accumulate(begin(has_star), end(has_star), 0));
            }
        }
        if (row_ans == INT_MAX) return -1;
        ans += row_ans;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) cout << solve() << "\n";
}

Subtask 3

Note that black and white pixels immediately imply that certain locations do or do not contain stars, so let's deal with them first and the gray pixels later. More specifically,

1. Place all stars required to satisfy black pixels.
2. Check whether there are any unsatisfied white pixels.
3. Add stars to satisfy gray pixels, without causing any white pixels to be unsatisfied.

The first two steps are straightforward, while the last can be accomplished using a greedy approach. While there is an unsatisfied gray pixel, consider the leftmost such gray pixel - then we must choose to place a star in at least one of two locations (at the gray pixel, or to the left of it). It is always optimal to place a star at the gray pixel due to the following reasons:

1. The location to the left of that pixel might be outside of the grid or correspond to the white pixel, so it might not be available.
2. A star at that gray pixel can potentially satisfy a gray pixel to the right, whereas a star to the left of that gray pixel will not.

This approach can be implemented with two left-to-right passes over each row of the input grid, the first for the black pixels and the second for the remaining pixels. The runtime per test is $O(N^2)$.

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

int solve() {
    int N, A, B;
    cin >> N >> A >> B;
    vector<string> rows(N);
    for (auto &row : rows) cin >> row;
    assert(A == 1 && B == 0);
    int ans = 0;
    for (const auto &row : rows) {
        vector<bool> has_star(N);
        for (int c = 0; c < N; ++c) {
            if (row[c] == 'B') {
                if (c == 0) return -1;
                has_star[c - 1] = has_star[c] = true;
            }
        }
        for (int c = 0; c < N; ++c) {
            if (row[c] == 'W') {
                if (has_star[c]) return -1;
            } else if (row[c] == 'G') {
                if (has_star[c]) continue;
                if (c && has_star[c - 1]) continue;
                has_star[c] = true;
            }
        }
        ans += accumulate(begin(has_star), end(has_star), 0);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) cout << solve() << "\n";
}

Full Solution

This can be solved using pretty much the same method as subtask 3 (iterate over the grid once to process all black pixels, then again to process all remaining pixels). We can process the pixels in any order as long as pixel $(r,c)$ is never processed before pixel $(r-B, c-A)$.

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

int solve() {
    int N, A, B;
    cin >> N >> A >> B;
    vector<string> rows(N);
    for (auto &row : rows) cin >> row;
    vector<vector<bool>> has_star(N, vector<bool>(N));
    for (int r = 0; r < N; ++r)
        for (int c = 0; c < N; ++c)
            if (rows[r][c] == 'B') {
                if (r - B < 0 || c - A < 0) return -1;
                has_star[r][c] = has_star[r - B][c - A] = 1;
            }
    for (int r = 0; r < N; ++r)
        for (int c = 0; c < N; ++c) {
            if (rows[r][c] == 'W') {
                if (has_star[r][c]) return -1;
            } else if (rows[r][c] == 'G') {
                if (has_star[r][c]) continue;
                if (r >= B && c >= A && has_star[r - B][c - A]) continue;
                has_star[r][c] = true;
            }
        }
    int ans = 0;
    for (const auto &row : has_star) ans += accumulate(begin(row), end(row), 0);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) cout << solve() << "\n";
}

Brandon Wang's Python code:

CTI = {"W": 0, "G": 1, "B": 2}
 
def tc():
    N, A, B = [int(x) for x in input().split()]
    grid = [[CTI[x] for x in input()] for _ in range(N)]
    stars = [[0 for _ in range(N)] for _ in range(N)]
 
    for i in range(N):
        for j in range(N):
            if grid[i][j] == 2:
                stars[i][j] = 1
                if i < B or j < A:
                    print(-1)
                    return
                if grid[i-B][j-A] == 0:
                    print(-1)
                    return
                stars[i-B][j-A] = 1
 
    for i in range(N):
        for j in range(N):
            if grid[i][j] == 1:
                if stars[i][j] == 1:
                    continue
                if i < B or j < A:
                    stars[i][j] = 1
                    continue
                if stars[i-B][j-A] == 1:
                    continue
                stars[i][j] = 1
                    
    print(sum(sum(x) for x in stars))
 
T = int(input())
 
while T > 0:
    T -= 1
    tc()