Submission #1520415

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#define REP(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 1
#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR
#endif

//改造
typedef long long int ll;
using namespace std;

//ここから編集する
struct zahyou {
    int x;
    int y;
};

stack<zahyou> st;

bool dfs(int board[][8], int q_num) {

    int cboard[8][8];
    if (q_num == 8) return true;

    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            cboard[i][j] = board[i][j];
        }
    }

    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if (board[i][j] == 0) {

                zahyou zahyou1;
                zahyou1.x = j;
                zahyou1.y = i;
                st.push(zahyou1);
//                cboard[i][j] = 1;
                for (int k = 0; k < 8; k++) {
                    for (int l = 0; l < 8; l++) {
                        if (i == k || l == j || abs(i - k) == abs(l - j)) {
                            cboard[k][l] = 1;
                        }
                    }
                }
                q_num++;
                if (dfs(cboard, q_num)) {
                    return true;

                }
                q_num--;
                st.pop();
                for (int i = 0; i < 8; i++) {
                    for (int j = 0; j < 8; j++) {
                        cboard[i][j] = board[i][j];
                    }
                }
//                return dfs(cboard,q_num);
            }
        }
    }
//    st.pop();
    return false;
}

int main() {
    int board[8][8] = {};
    int q_num = 0;
    for (int i = 0; i < 64; i++) {
        char tmp;
        cin >> tmp;
        if (tmp == 'Q') {
            q_num++;
            zahyou zahyou1;
            zahyou1.x = i % 8;
            zahyou1.y = i / 8;
            st.push(zahyou1);
            if (board[i / 8][i % 8] == 1) {
                cout << "No Answer" << endl;
                return 0;
            }
//            for (int j = 0; j < 8; j++) {
//                board[j][i % 8] = 1;
//                board[i / 8][j] = 1;
////                for(int k = 0; k < 8; k++){
////                }
//            }
            for (int j = 0; j < 64; j++) {
                if (j / 8 == i / 8 || j % 8 == i % 8 ||
                    abs(j % 8 - i % 8) == abs(j / 8 - i / 8)) {
                    board[j / 8][j % 8] = 1;
                }
            }
        }

    }

    if (!dfs(board, q_num)) {
        cout << "No Answer" << endl;
        return 0;
    }

    char ret[8][8];
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            ret[i][j] = '.';
        }
    }
    while (!st.empty()) {
//        ret[st.top().x][st.top().y] = 'Q';
        ret[st.top().y][st.top().x] = 'Q';
        st.pop();
    }
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            cout << ret[i][j];
        }
        cout << endl;
    }
}

Submission Info

Judge Result