Submission #1177740

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdouble vector<double>
#define vstring vector<string>
using namespace std;

#include<map>
#include<set>
#include<queue>

typedef long long ll;
typedef unsigned long long ull;
 
const int n = 8;
 
bool putQueen(int h, int w, vector<string>& c) {
	c[h][w] = 'Q';

	// Qがおけない場所は.にしてゆく

	// 行チェック
	rep(i,n) {
		if (i == w) continue;
		if (c[h][i] == 'Q') return false;
		c[h][i] = '.';
	}

	// 列チェック
	rep(i,n) {
		if (i == h) continue;
		if (c[i][w] == 'Q') return false;
		c[i][w] = '.';
	}	

	// 右上方向斜めチェック
	rep(i,n) {
		if (i == h) continue;
		int j = w + i - h;
		if (j < 0 || j >= n) continue;
		if (c[i][j] == 'Q') return false;
		c[i][j] = '.'
		;
	}

	// 右下方向斜めチェック
	rep(j,n) {
		if (j == w) continue;
		int i = h + w - j;
		if (i < 0 || i >= n) continue;
		if (c[i][j] == 'Q') return false;
		c[i][j] = '.';
	}

	return true;
}
 
void printBoard(vector<string>& c) {
	rep(i,n) cout << c[i] << endl;
}
 
bool dfs(int h, int w, vector<string> c, int cnt) {
	if (!putQueen(h, w, c)) return false;
	
	cnt--;
	if (cnt == 0) {
		printBoard(c);
		return true;
	}

	rep(i,n) {
		rep(j,n) {
			if (c[i][j] != 'o') continue;
			if (dfs(i, j, c, cnt)) return true;
		}
	}
	return false;
}
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	vector<string> c(n);
	
	rep(i,n) cin >> c[i];

	// Qがおける場所をoとする
	// いったんすべての.をoとする
	rep(i,n){
		rep(j,n){
			if (c[i][j] == '.') c[i][j] = 'o';
		}
	}

	//初期状態チェック
	rep(i,n){
		rep(j,n) {
			if (c[i][j] == 'Q' && !putQueen(i, j, c)) {
				cout << "No Answer" << endl;
				return 0;
			}
		}
	}

	rep(i,n) {
		rep(j,n) {
			if (c[i][j] == 'o' && dfs(i, j, c, 5))
				return 0;
		}
	}

	cout << "No Answer" << endl;
	return 0;
}

Submission Info

Judge Result