Submission #47062366

---

Source Code Expand

#include <bits/stdc++.h>

namespace {
using Num = long long int;
using Grid = std::vector<std::string>;
constexpr Num SizeOfCandidates = 3;
Num n {0};
std::string rows;
std::string cols;
}

std::optional<Grid> visit_dfs(Grid& grid, Num current) {
    const std::optional<Grid> zero;

    if (current >= (n * n)) {
        bool failed {false};
        for(Num x{0}; !failed && (x<n); ++x) {
            char first {'.'};
            std::array<Num, SizeOfCandidates> counts {0,0,0};

            for(Num y{0}; !failed && (y<n); ++y) {
                const char c = grid.at(y).at(x);
                if (c == '.') {
                    continue;
                }
                first = (first == '.') ? c : first;
                counts.at(c - 'A') += 1;
            }

            failed |= (first != cols.at(x)) ||
                std::any_of(counts.begin(), counts.end(),
                            [](const auto& a) { return a != 1; });
        }

        if (failed) {
            return zero;
        }

        return grid;
    }

    const Num y = current / n;
    const Num x = current % n;
    const auto prev_value = grid[y][x];
    std::array<Num, SizeOfCandidates> counts {0,0,0};
    Num total {0};

    for(Num i{0}; i<x; ++i) {
        const char c = grid.at(y).at(i);
        if (c == '.') {
            continue;
        }

        counts.at(c - 'A') += 1;
        ++total;
    }

    std::vector<char> candidates;
    candidates.reserve(4);
    if ((n - x) > (SizeOfCandidates - total)) {
        candidates.push_back('.');
    }

    if (total == 0) {
        candidates.push_back(rows.at(y));
    } else {
        for(Num i{0}; i<SizeOfCandidates; ++i) {
            if (counts.at(i) == 0) {
                candidates.push_back('A' + i);
            }
        }
    }

    for(const auto& value : candidates) {
        grid[y][x] = value;
        const auto result = visit_dfs(grid, current + 1);

        if (result.has_value()) {
            return result;
        }

        grid[y][x] = prev_value;
    }

    return zero;
}

void solve(std::istream& is, std::ostream& os) {
    is >> n >> rows >> cols;

    Grid grid(n);
    for(auto&& s : grid) {
        s.resize(n, '.');
    }

    const auto answer = visit_dfs(grid, 0);
    if (answer.has_value()) {
        os << "Yes\n";
        for(const auto& s : grid) {
            os << s << "\n";
        }
    } else {
        os << "No\n";
    }
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

Submission Info

Judge Result