Submission #1179905

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;
typedef long long lli;
int dx[] = {1,1,0,-1,-1,-1,0,1};
int dy[] = {0,1,1,1,0,-1,-1,-1};
vector<string> c(8);
vector<string> ans;
bool canPut(lli x,lli y,vector<string>& c){
    for(lli i = 0;i < 8;i++){
        lli t = x+dx[i],s = y+dy[i];
        while(t >= 0 && t < 8 && s >= 0 && s < 8){
            if(c[t][s] == 'Q') return false;
            t += dx[i];s += dy[i];
        }
    }   
    return true;
}
void aim(lli x,lli y,vector<string>& c){
    c[x][y] = 'Q';
    for(lli i = 0;i < 8;i++){
        lli t = x+dx[i],s = y+dy[i];
        while(t >= 0 && t < 8 && s >= 0 && s < 8){
            c[t][s] = '#';
            t += dx[i];s += dy[i];
        }
    }
}
int main(){
    for(lli i = 0;i < 8;i++) cin >> c[i];
    ans = c;
    for(lli i = 0;i < 8;i++){
        for(lli j = 0;j < 8;j++){
            if(c[i][j] == 'Q'){
                if(canPut(i,j,c)) aim(i,j,c);
                else {
                    cout << "No Answer" << endl;
                    return 0;
                }
            }
        }
    }
    for(lli i1 = 0;i1 < 64;i1++){
        vector<string> c1 = c;
        while(i1 < 64 && c1[i1/8][i1%8] != '.' && !canPut(i1/8,i1%8,c1)) i1++;
        aim(i1/8,i1&8,c1);
    for(lli i2 = i1+1;i2 < 64;i2++){
        vector<string> c2 = c1;
        while(i2 < 64 && c2[i2/8][i2%8] != '.' && !canPut(i2/8,i2%8,c2)) i2++;
        aim(i2/8,i2%8,c2);
    for(lli i3 = i2+1;i3 < 64;i3++){
        vector<string> c3 = c2;
        while(i3 < 64 && c3[i3/8][i3%8] != '.' && !canPut(i3/8,i3%8,c3)) i3++;
        aim(i3/8,i3%8,c3);
    for(lli i4 = i3+1;i4 < 64;i4++){
        vector<string> c4 = c3;
        while(i4 < 64 && c4[i4/8][i4%8] != '.' && !canPut(i4/8,i4%8,c4)) i4++;
        aim(i4/8,i4%8,c4);
    for(lli i5 = i4+1;i5 < 64;i5++){
        vector<string> c5 = c4;
        while(i5 < 64 && c5[i5/8][i5%8] != '.' && !canPut(i5/8,i5%8,c5)) i5++;
        if(i5 == 64) break;
        else {
            ans[i1/8][i1%8] = 'Q';
            ans[i2/8][i2%8] = 'Q';
            ans[i3/8][i3%8] = 'Q';
            ans[i4/8][i4%8] = 'Q';
            ans[i5/8][i5%8] = 'Q';
            for(lli i = 0;i < 8;i++){
                cout << ans[i] << endl;
            }
            return 0;
        }
    }
    }
    }
    }
    }
    cout << "No Answer" << endl;
    return 0;
}

Submission Info

Judge Result