Submission #6872427
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define all(a) (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }
template<class Type>struct is_vector : std::false_type {};
template<class ValueType, class Alloc>struct is_vector<std::vector<ValueType, Alloc>> : std::true_type {};
template <typename T> inline ostream& operator << (ostream& out, const vector<T>& v) {
if (v.empty())return out;
constexpr bool is_vector_v = is_vector<T>::value;
if (is_vector_v)for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? "\n" : "");
else for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? " " : "");
return out;
}
inline void put() {}
template<class T> inline void put(const T& first) { std::cout << first; printf("\n"); }
template<class T, class... N> inline void put(const T& first, const N& ... rest) { std::cout << first; printf(" "); put(rest...); }
inline void putn() {}
template<class T, class... N> inline void putn(const T& first, const N& ... rest) { std::cout << first; printf("\n"); putn(rest...); }
int main() {
vector<string> s(8);
REP(i, 8) {
cin >> s[i];
}
vector<vector<int>> a(8, vector<int>(8, 0));
int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
int dy[8] = { 0,1,1,1,0,-1,-1,-1 };
vector<int> c(8, 0);
REP(i, 8) {
REP(j, 8) {
if (s[i][j] == 'Q') {
REP(k, 8) {
REP(l, 8) {
int ny = i + dy[l] * k;
int nx = j + dx[l] * k;
if (0 <= ny && ny < 8 && 0 <= nx && nx < 8) {
a[ny][nx] = 1;
if (k != 0 && s[ny][nx] == 'Q') {
put("No Answer");
return 0;
}
}
}
}
c[j] = 1;
}
}
}
vector<int> p;
REP(i, 8) {
if (c[i] == 0) {
p.push_back(i);
}
}
REP(i1, 8) {
REP(i2, 8) {
REP(i3, 8) {
REP(i4, 8) {
REP(i5, 8) {
vector<vector<int>> b = a;
vector<string> s1 = s;
bool flag;
flag = true;
for (int k = 0; k < 8 && flag; ++k) {
for (int l = 0; l < 8 && flag; ++l) {
int ny = i1 + dy[l] * k;
int nx = p[0] + dx[l] * k;
if (0 <= ny && ny < 8 && 0 <= nx && nx < 8) {
b[ny][nx] = 1;
if (k != 0 && s1[ny][nx] == 'Q') {
flag = false;
}
}
}
}
if (!flag) {
continue;
}
s1[i1][p[0]] = 'Q';
flag = true;
for (int k = 0; k < 8 && flag; ++k) {
for (int l = 0; l < 8 && flag; ++l) {
int ny = i2 + dy[l] * k;
int nx = p[1] + dx[l] * k;
if (0 <= ny && ny < 8 && 0 <= nx && nx < 8) {
b[ny][nx] = 1;
if (k != 0 && s1[ny][nx] == 'Q') {
flag = false;
}
}
}
}
if (!flag) {
continue;
}
s1[i2][p[1]] = 'Q';
flag = true;
for (int k = 0; k < 8 && flag; ++k) {
for (int l = 0; l < 8 && flag; ++l) {
int ny = i3 + dy[l] * k;
int nx = p[2] + dx[l] * k;
if (0 <= ny && ny < 8 && 0 <= nx && nx < 8) {
b[ny][nx] = 1;
if (k != 0 && s1[ny][nx] == 'Q') {
flag = false;
}
}
}
}
if (!flag) {
continue;
}
s1[i3][p[2]] = 'Q';
flag = true;
for (int k = 0; k < 8 && flag; ++k) {
for (int l = 0; l < 8 && flag; ++l) {
int ny = i4 + dy[l] * k;
int nx = p[3] + dx[l] * k;
if (0 <= ny && ny < 8 && 0 <= nx && nx < 8) {
b[ny][nx] = 1;
if (k != 0 && s1[ny][nx] == 'Q') {
flag = false;
}
}
}
}
if (!flag) {
continue;
}
s1[i4][p[3]] = 'Q';
flag = true;
for (int k = 0; k < 8 && flag; ++k) {
for (int l = 0; l < 8 && flag; ++l) {
int ny = i5 + dy[l] * k;
int nx = p[4] + dx[l] * k;
if (0 <= ny && ny < 8 && 0 <= nx && nx < 8) {
b[ny][nx] = 1;
if (k != 0 && s1[ny][nx] == 'Q') {
flag = false;
}
}
}
}
if (!flag) {
continue;
}
s1[i5][p[4]] = 'Q';
REP(i, 8) {
put(s1[i]);
}
return 0;
}
}
}
}
}
put("No Answer");
return 0;
}
Submission Info
Submission Time |
|
Task |
C - パズルのお手伝い |
User |
idaten |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
5059 Byte |
Status |
AC |
Exec Time |
32 ms |
Memory |
256 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00_sample1.txt, 00_sample2.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 01_rnd_21.txt, 01_rnd_22.txt, 01_rnd_23.txt, 01_rnd_24.txt, 01_rnd_25.txt, 01_rnd_26.txt, 01_rnd_27.txt, 01_rnd_28.txt, 01_rnd_29.txt, 01_rnd_30.txt, 01_rnd_31.txt, 01_rnd_32.txt, 01_rnd_33.txt, 01_rnd_34.txt, 01_rnd_35.txt, 01_rnd_36.txt, 01_rnd_37.txt, 01_rnd_38.txt, 01_rnd_39.txt |
Case Name |
Status |
Exec Time |
Memory |
00_sample1.txt |
AC |
5 ms |
256 KB |
00_sample2.txt |
AC |
1 ms |
256 KB |
01_rnd_00.txt |
AC |
31 ms |
256 KB |
01_rnd_01.txt |
AC |
3 ms |
256 KB |
01_rnd_02.txt |
AC |
1 ms |
256 KB |
01_rnd_03.txt |
AC |
30 ms |
256 KB |
01_rnd_04.txt |
AC |
1 ms |
256 KB |
01_rnd_05.txt |
AC |
32 ms |
256 KB |
01_rnd_06.txt |
AC |
1 ms |
256 KB |
01_rnd_07.txt |
AC |
1 ms |
256 KB |
01_rnd_08.txt |
AC |
1 ms |
256 KB |
01_rnd_09.txt |
AC |
1 ms |
256 KB |
01_rnd_10.txt |
AC |
1 ms |
256 KB |
01_rnd_11.txt |
AC |
1 ms |
256 KB |
01_rnd_12.txt |
AC |
1 ms |
256 KB |
01_rnd_13.txt |
AC |
24 ms |
256 KB |
01_rnd_14.txt |
AC |
1 ms |
256 KB |
01_rnd_15.txt |
AC |
1 ms |
256 KB |
01_rnd_16.txt |
AC |
1 ms |
256 KB |
01_rnd_17.txt |
AC |
1 ms |
256 KB |
01_rnd_18.txt |
AC |
19 ms |
256 KB |
01_rnd_19.txt |
AC |
19 ms |
256 KB |
01_rnd_20.txt |
AC |
1 ms |
256 KB |
01_rnd_21.txt |
AC |
1 ms |
256 KB |
01_rnd_22.txt |
AC |
1 ms |
256 KB |
01_rnd_23.txt |
AC |
31 ms |
256 KB |
01_rnd_24.txt |
AC |
1 ms |
256 KB |
01_rnd_25.txt |
AC |
17 ms |
256 KB |
01_rnd_26.txt |
AC |
1 ms |
256 KB |
01_rnd_27.txt |
AC |
8 ms |
256 KB |
01_rnd_28.txt |
AC |
30 ms |
256 KB |
01_rnd_29.txt |
AC |
1 ms |
256 KB |
01_rnd_30.txt |
AC |
1 ms |
256 KB |
01_rnd_31.txt |
AC |
1 ms |
256 KB |
01_rnd_32.txt |
AC |
23 ms |
256 KB |
01_rnd_33.txt |
AC |
1 ms |
256 KB |
01_rnd_34.txt |
AC |
1 ms |
256 KB |
01_rnd_35.txt |
AC |
1 ms |
256 KB |
01_rnd_36.txt |
AC |
1 ms |
256 KB |
01_rnd_37.txt |
AC |
1 ms |
256 KB |
01_rnd_38.txt |
AC |
31 ms |
256 KB |
01_rnd_39.txt |
AC |
32 ms |
256 KB |