同時にコマを置くことができない \(2\) マスの間に辺を張ったグラフを考えると、このグラフの最大独立集合が求めるコマの配置です。

マス目を適切に \(2\) 色で塗り分けることで、同時にコマを置くことができないどの \(2\) マスの組も異なる色をもつようにできることを示します（つまり、上で考えたグラフが二部グラフになることを示します）。 \(N\times N\) のマス目がすべて空きマスであるときに示せばよいため、これを示します。

\(A,B\) が互いに素でないとき、最大公約数 \(g\) に対して \((\lfloor i/g\rfloor,\lfloor j/g\rfloor)\) が等しいようなマス \((i,j)\) は同じ色で塗ることで、\(A,B\) が互いに素であるときの条件に帰着することができます。 \(A,B\) がどちらも奇数であるとき、\(i\) を \(2\) で割った余りによって マス \((i,j)\) の色を塗ればよいです。 \(A,B\) の一方のみが奇数であるとき、\(i+j\) を \(2\) で割った余りによって マス \((i,j)\) の色を塗ればよいです。

よって、求めるべきものは二部グラフの最大独立集合です。 二部グラフの最大独立集合は、最大流アルゴリズムを用いて求められることが知られています。 超頂点を追加して最大流を求め、そこから求めた最小カットとそれぞれの部集合との共通部分が求める最大独立集合となります。

アルゴリズムの詳細やその証明は最大独立集合問題のアルゴリズム 9 二部グラフの最大独立集合 - 37zigenやネットワークフロー入門 - hos_lyricを参照してください。

実装例は以下のようになります。

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

int main() {
    using namespace std;
    unsigned N, A, B;
    cin >> N >> A >> B;
    // block × block マスを一塊にして塗る
    const auto block{(A | B) & -(A | B)};

    // 最大流を求めるグラフ：ソース + マス目 + シンク
    atcoder::mf_graph<int> graph(1 + N * N + 1);

    // 盤面を読み込む
    const auto field = views::istream<string>(cin) | ranges::to<vector<string>>();

    // それぞれの空きマスについて、ソースかシンクとの間に辺を張る
    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);

    // 同時に置くことができない空きマスの組の間に辺を張る
    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);

    // フローを流し、最大独立集合を求める
    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;
}