Consider the graph obtained by adding two cells where pieces cannot be placed simultaneously. Then the sought placement of pieces is a maximum independent set of this graph.

We will show that one can paint the cells in two colors so that any two cells where pieces cannot be placed simultaneously have different colors. (In other words, we will show that the graph defined above is a bipartite graph.) It suffices to prove it when the \(N\times N\) cells are all empty, so we will show that.

When \(A\) and \(B\) are not coprime, for their greatest common divisor \(g\) one can paint cells \((i,j)\) having the same \((\lfloor i/g\rfloor,\lfloor j/g\rfloor)\) in the same color, so that the claim is reduced to the case where \(A\) and \(B\) are coprime. When \(A\) and \(B\) are both odd, we can paint \((i,j)\) according to the parity of \(i\). If only one of \(A\) and \(B\) is odd, we can paint \(((i,j)\( according to the parity of \((i+j)\).

Thus, what we need to find is a maximum independent set of the bipartite graph. It is known that a maximum independent set of a bipartite graph can be found using the maximum flow algorithm. Add additional vertices and find a maximum flow, which gives us a minimum cut. The intersection of the minimum cut and each part is the sought maximum independent set.

For more details on the algorithm, refer to articles such as 最大独立集合問題のアルゴリズム 9 二部グラフの最大独立集合 - 37zigen and ネットワークフロー入門 - hos_lyric (both in Japanese).

The following is sample code.

#include <iostream>
#include <ranges>
#include <vector>
#include <utility>
#include <atcoder/maxflow>

int main() {
    using namespace std;
    unsigned N, A, B;
    cin >> N >> A >> B;
    // Paint block × block at once
    const auto block{(A | B) & -(A | B)};

    // Graph to find maximum flow: source + grid + sink
    atcoder::mf_graph<int> graph(1 + N * N + 1);

    // read the board
    const auto field = views::istream<string>(cin) | ranges::to<vector<string>>();

    // From each empty cell, add an edge to the source or sink
    for (const auto& [i, j] : views::cartesian_product(views::iota(0U, N), views::iota(0U, N)) |
                              views::filter([&field](const auto& box) {
                                  const auto& [i, j]{box};
                                  return field[i][j] == '.';
                              }))
        if (block & (i ^ j & (A ^ B)))
            graph.add_edge(0, 1 + i * N + j, 1);
        else
            graph.add_edge(1 + i * N + j, 1 + N * N, 1);

    // Add edges between cells where placing pieces to both are forbidden
    for (const auto& [di, dj] : vector<pair<unsigned, unsigned>>{{A, B}, {B, A}, {-B, A}, {-A, B}})
        for (const auto& [i, j] : views::cartesian_product(views::iota(0U, N), views::iota(0U, N)) |
                                  views::filter([N, di, dj, &field](const auto& box) {
                                      const auto& [i, j]{box};
                                      return i + di < N && j + dj < N && field[i][j] == '.' && field[i + di][j + dj] == '.';
                                  }))
            if (block & (i ^ j & (A ^ B)))
                graph.add_edge(1 + i * N + j, 1 + (i + di) * N + j + dj, 1);
            else
                graph.add_edge(1 + (i + di) * N + j + dj, 1 + i * N + j, 1);

    // Push the flow to find a maximum independent set
    graph.flow(0, 1 + N * N);
    for (const auto min_cut{graph.min_cut(0)}; const auto i : views::iota(0U, N)) {
        for (const auto j : views::iota(0U, N))
            if (field[i][j] == '#')
                cout << '#';
            else if (block & (i ^ j & (A ^ B)))
                cout << (min_cut[1 + i * N + j] ? 'o' : '.');
            else
                cout << (min_cut[1 + i * N + j] ? '.' : 'o');
        cout << endl;
    }
    return 0;
}