Submission #2246704

---

Source Code Expand

#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)

using namespace std;

typedef pair<int, int> p;

const int inf = 1e15;
const int mod = 1e9+7;

void search(vector<p> q, vector<bool> h, vector<bool> w, int d){
    if(d == 5){
        vector<vector<char>> ans(8, vector<char>(8, '.'));
        for(int i = 0; i < 8; i++){
            ans[q[i].first][q[i].second] = 'q';
        }
        rep(i, 8){
            rep(j, 8){
                cout << ans[i][j];
            }
            cout << endl;
        }
        exit(0);
    }

    for(int i = 0; i < 8; i++){
        if(h[i]){
            continue;
        }

        for(int j = 0; j < 8; j++){
            if(w[j]){
                continue;
            }

            bool f = true;
            for(int k = 0; k < (int)q.size(); k++){
                int sx = abs(q[k].first - i);
                int sy = abs(q[k].second - j);
                if(sx == sy){
                    f = false;
                }
            }
            if(f){
                q.push_back(make_pair(i, j));
                h[i] = true;
                w[j] = true;
                search(q, h, w, d+1);
                q.pop_back();
                h[i] = false;
                w[j] = false;
            }
        }
    }
}

signed main(){
    vector<bool> h(8, false), w(8, false);

    vector<p> q;
    rep(i, 8){
        rep(j, 8){
            char c;
            cin >> c;
            if(c == 'q'){
                h[i] = true;
                w[j] = true;
                q.push_back(make_pair(i, j));
            }
        }
    }

    for(int i = 0; i < (int)q.size(); i++){
        for(int j = 0; j < (int)q.size(); j++){
            if(i == j){
                continue;
            }
            int sx = abs(q[i].first - q[j].first);
            int sy = abs(q[i].second - q[j].second);
            if(sx == sy){
                cout << "no answer" << endl;
                return 0;
            }
        }
    }

    search(q, h, w, 0);
    return 0;
}

Submission Info

Judge Result