Submission #7025100

---

Source Code Expand

#include <bits/stdc++.h>

#define CEIL(a,b) ((a) / (b) + ((a) % (b) == 0 ? 0 : 1))

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using a5 = array<pii, 5>;
using a8 = array<int, 8>;
using a15 = array<int, 15>;

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'000'000'001;
constexpr ll LLINF = 4'000'000'000'000'000'001;
// constexpr int INF = 2147483647; // 2 * 1e9
// constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1, 0};

bool ok(a5 &ps) {
    for(int i = 0; i < 5; ++i) {
        if(ps[i] == make_pair(0, 0)) return false;
    }
    return true;
}

a5 calc(a5 &ps, a8 &xs, a8 &ys, a15 &wa, a15 &sa) {
    for(int i = 0; i < 5; ++i) {
        if(ps[i] == make_pair(0, 0)) {
            for(int x = 1; x <= 8; ++x) {
                for(int y = 1; y <= 8; ++y){
                    if(xs[x-1] || ys[y-1] || wa[x + y - 2] || sa[x - y + 7]) continue;
                    xs[x-1] = 1;
                    ys[y-1] = 1;
                    wa[x + y - 2] = 1;
                    sa[x - y + 7] = 1;
                    ps[i] = make_pair(x, y);
                    auto result = calc(ps, xs, ys, wa, sa);
                    if(ok(result)) return result;
                    xs[x-1] = 0;
                    ys[y-1] = 0;
                    wa[x + y - 2] = 0;
                    sa[x - y + 7] = 0;
                    ps[i] = make_pair(0, 0);
                }
            }
        }
    }
    return ps;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    vector<string> c(8);
    for(int i = 0; i < 8; ++i){
        cin >> c[i];
    }
    a8 x = {0}, y = {0};
    a15 wa = {0}, sa = {0};
    for(int i = 0; i < 8; ++i){
        for(int j = 0; j < 8; ++j){
            if(c[i][j] == 'Q') {
                ++x[j];
                ++y[i];
                ++wa[i + j];
                ++sa[j - i + 7];
            }
        }
    }
    for(int i = 0; i < 8; ++i) {
        if(x[i] >= 2 || y[i] >= 2) {
            cout << "No Answer\n";
            return 0;
        }
    }
    for(int i = 0; i < 15; ++i) {
        if(wa[i] >= 2 || sa[i] >= 2) {
            cout << "No Answer\n";
            return 0;
        }
    }
    a5 ps;
    a5 result = calc(ps, x, y, wa, sa);
    if(!ok(result)) {
            cout << "No Answer\n";
            return 0;
    }
    else {
        for(auto && p : result){
            c[p.second - 1][p.first - 1] = 'Q';
        }
    }
    for(int i = 0; i < 8; ++i){
        cout << c[i] << "\n";
    }
    return 0;
}

Submission Info

Judge Result