[AtCoder] ARC 001 C – パズルのお手伝い

2020年9月17日2020年12月13日

問題

方針

\( 8 \) クイーン問題です。深さ優先探索によって解答します。初期値が当てられたとき、配置が可能かに注意します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

char c[8][8];

int dx[] = {-1, -1, 1, 1};
int dy[] = {-1, 1, -1, 1};
bool flag_row[8]{};
bool flag_col[8]{};
bool flag = false;

bool can_put(int h, int w) {
    for (int i = 0; i < 4; i++) {
        for (int j = 1; j < 8; j++) {
            int y = h + dy[i] * j;
            int x = w + dx[i] * j;
            if (y < 0 || y > 7 || x < 0 || x > 7) continue;
            if (c[y][x] == 'Q') return false;
        }
    }
    return true;
}

void disp() {
    for (int i = 0; i < 8; i++) {
        if (!flag_row[i] || !flag_col[i]) {
            flag = false;
            return;
        }
    }
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            cout << c[i][j];
        }
        cout << "\n";
    }
}

void solve(int n) {
    if (flag) return;
    if (n == 5) {
        flag = true;
        disp();
        return;
    }
    for (int i = 0; i < 8; i++) {
        if (flag_row[i]) continue;
        for (int j = 0; j < 8; j++) {
            if (flag_col[j]) continue;
            if (can_put(i, j)) {
                c[i][j] = 'Q';
                flag_row[i] = true;
                flag_col[j] = true;
                solve(n + 1);
                c[i][j] = '.';
                flag_row[i] = false;
                flag_col[j] = false;
            }
        }
    }
}

int main() {
    
    for (int i = 0; i < 8; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < 8; j++) {
            c[i][j] = s[j];
            if (s[j] == 'Q') {
                if (flag_row[i] || flag_col[j]) {
                    flag = true;
                }
                if (!can_put(i, j)) {
                    flag = true;
                }
                flag_row[i] = true;
                flag_col[j] = true;
            }
        }
    }
    if (flag) {
        cout << "No Answer\n";
        return 0;
    }
    solve(0);
    if (!flag) {
        cout << "No Answer\n";
    }
    return 0;
}

感想

解法はすぐに思い付いたというか知っていましたが、抜けがあって手間取りました。