Submission #1179925

---

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];
        }
    }
}
lli dfs(lli i,vector<string> c,lli k){
    for(;i < 64;i++){
        if(c[i/8][i%8] == '.'){
            if(k == 1){
                ans[i/8][i%8] = 'Q';
                return i;
            }
            vector<string> c_ = c;
            aim(i/8,i%8,c_);
            if(dfs(i+1,c_,k-1) < 64){
                ans[i/8][i%8] = 'Q';
                return i;
            }
        }
    }
    return 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)){
                    cout << "No Answer" << endl;
                    return 0;
                }
            }
        }
    }
    for(lli i = 0;i < 8;i++){
        for(lli j = 0;j < 8;j++){
            if(c[i][j] == 'Q') aim(i,j,c);
        }
    }

    if(dfs(0,c,5) < 64){
        for(lli i = 0;i < 8;i++){
            cout << ans[i] << endl;
        }
    }else{
        cout << "No Answer" << endl;
    }
    return 0;
}

Submission Info

Judge Result