ALDS1_13_A - 雑記･まとめ

有名な8クイーン問題

・同じ行、同じ列にクイーンを置かないこと

・左斜め上、左斜め下、右斜め上、右斜め下にクイーンを置かないこと

上記2点を満たせばよい。

・同じ行、同じ列にクイーンを置かないこと

⇒順列そのままで全列挙可能なので判定は不要

・左斜め上、左斜め下、右斜め上、右斜め下にクイーンを置かないこと

⇒4ベクトル方向に探索

条件1は順列のみで実現出来るのであとは8個のクイーンが全て条件2を満たせばOK

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

int k, r[9], c[9];
int board[9][9];
int dx = {1, -1, 1, -1};
int dy = {1, 1, -1, -1};
vector < int > v;

void print(){

    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            if(board[i][j] == 1) cout << "Q";
            else cout << ".";
        }
        cout << endl;
    }
    
    return;
}
bool judge(int y, int x){

    bool flg = true;
    for(int i=0;i<4;i++){
        int ny = y, nx = x;
        while(true){
            ny += dy[i], nx += dx[i];
            if(ny < 0 || ny > 8 || nx < 0 || nx > 8) break;
            if(board[ny][nx] == 1){
                flg = false;
                break;
            }
        }
    }

    return flg;
}

int main(){

    cin >> k;
    for(int i=0;i<k;i++) cin >> r[i] >> c[i];
    for(int i=0;i<8;i++) v.push_back(i);

    do{

        bool flg = true;
        memset(board, 0, sizeof(board));

        for(int i=0;i<8;i++){
            int y = i, x = v[i];

            board[y][x] = 1;

            for(int j=0;j<k;j++){
                if(r[j] == y && c[j] != x) flg = false;
            }

            flg &= judge(y, x);
            if(!flg) break;
        }

        if(flg){
            print();
            break;
        }

    }while(next_permutation(v.begin(), v.end()));
}