Submission #1757701

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

using vc = vector<char>;
using vvc = vector<vector<char>>;

int dic[5] = {1,1,-1,-1,1};

bool inside(int a){
    return ((a >= 0) && (a < 8)) ;
}

void paint(int y,int x,vvc& arr){
    for(int k = 0; k < 8; k++)
        arr[k][x] = arr[y][k] = ' ';
    
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 8; j++){
            if(inside(y+dic[i]*j) && inside(x+dic[i+1]*j)){
                arr[y+dic[i]*j][x+dic[i+1]*j] = ' ';
            }
        }
    }
    
    arr[y][x] = 'Q';
    return;
}

void output(vvc& now){

    for(int i = 0; i < 8; i++){
        for(int j = 0; j < 8; j++){
            if(now[i][j] == 'Q')
                cout << 'Q';
            else
                cout << '.';//.
        }
        cout << endl;
    }
}

void display(vvc& now){

    cout << "-----------" << endl;
    for(int i = 0; i < 8; i++){
        for(int j = 0; j < 8; j++){
            cout << now[i][j];
        }
        cout << endl;
    }
    cout << "-----------" << endl << endl;
}

int main(void){
    
    vvc arr(8,vc(8));
    
    for(int i = 0; i < 8; i++)
        for(int j = 0; j < 8; j++){
            cin >> arr[i][j];
        }
        
    for(int i = 0; i < 8; i++)
        for(int j = 0; j < 8; j++)
            if(arr[i][j] == 'Q'){
                paint(i,j,arr);
            }
    
    queue<vvc> q;
    q.push(arr);
    
    while(!q.empty()){
        vvc now = q.front();
        q.pop();
        
        //display(now);
        
        int answer = 0;
        for(int i = 0; i < 8; i++)
            for(int j = 0; j < 8; j++){
                if( now[i][j] == '.' ){
                    vvc next = now;
                    paint(i,j,next);
                    q.push(next);
                }else{
                    if(now[i][j] == 'Q')
                        answer++;
                }
            }
        if(answer == 8){
            output(now);
            return 0;
        }
    }
    
    cout << "No Answer" << endl;
    
    return 0;
}

Submission Info

Judge Result