問題
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; } }