AtCoder Regular Contest 001 C - パズルのお手伝い

問題

 8クイーンパズルについて3つクイーンを置いた状況の盤面を与えるので、残り5つを制約を満たすように置けるならそのうち一つを出力せよ。

解法

 制約を満たすような置き方について全探索をする。各行、列、および右斜め左斜めのラインについてクイーンの数を記録していき、置けるところだけ考えてDFS。

反省

 特に詰まることもなく十数分でAC。ARCの3問目とは言っても難易度のバラつきは大きそう。

 全探索を真っ先に考えるという発想は基本なので大事。こういうサイズ感に慣れていればICPC2018のD問題とかもあっさり解けるのだろう。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

struct State {
    vector<ll> col, raw, diag1, diag2;
    vector<pair<ll, ll>> queens;
};

State ans;

bool solve(State st) {
    if (st.queens.size() == 8) {
        ans = st;
        return true;
    }

    //可能な置き方を探る
    for (ll i = 0; i < 8; i++) {
        if (st.col[i] == 1) {
            continue;
        }
        for (ll j = 0; j < 8; j++) {
            if (st.raw[j] == 1) {
                continue;
            }
            if (st.diag1[i + j] == 0 && st.diag2[i - j + 7] == 0) {
                auto copy = st;
                //置ける
                copy.col[i]++;
                copy.raw[j]++;
                copy.diag1[i + j]++;
                copy.diag2[i - j + 7]++;
                copy.queens.emplace_back(i, j);
                if (solve(copy)) {
                    return true;
                }
            }
        }
    }

    return false;
}

int main() {
    vector<string> c(8);
    for (ll i = 0; i < 8; i++) {
        cin >> c[i];
    }

    State st;
    st.col.resize(8, 0);
    st.raw.resize(8, 0);
    st.diag1.resize(15, 0);
    st.diag2.resize(15, 0);
    for (ll i = 0; i < 8; i++) {
        for (ll j = 0; j < 8; j++) {
            if (c[i][j] == 'Q') {
                bool flag = true;
                if (++st.col[i] == 2) {
                    flag = false;
                }
                if (++st.raw[j] == 2) {
                    flag = false;
                }
                if (++st.diag1[i + j] == 2) {
                    flag = false;
                }
                if (++st.diag2[i - j + 7] == 2) {
                    flag = false;
                }
                if (!flag) {
                    cout << "No Answer" << endl;
                    return 0;
                }
                st.queens.emplace_back(i, j);
            }
        }
    }

    if (solve(st)) {
        vector<string> result(8, "........");
        for (auto q : ans.queens) {
            result[q.first][q.second] = 'Q';
        }
        for (ll i = 0; i < 8; i++) {
            cout << result[i] << endl;
        }
    } else {
        cout << "No Answer" << endl;
    }
}