# 【CSES】1624. Chessboard and Queens

## [題目連結](https://cses.fi/problemset/task/1624)

## **時間複雜度**

* $O(1)$ = $8^8$ ≈ 1e8

## **解題想法**

這題的中心想法很簡單，這題在枚舉的時候可以先發現到一行一定只有一個皇后（因為一個皇后的攻擊範圍包含自己那一行的全部），同時我們將枚舉定成一個位置是不是可以放皇后這件事簡化成會不會被自己上方的皇后攻擊到，如此一來就只需要關注自己以下的部分。

除此之外，可以先將攻擊範圍繪製成以下這張圖

i   | 0 0 0 0 Q 0 0 0
i+1 | 0 0 0 X X X 0 0
i+2 | 0 0 X 0 X 0 X 0

從這張圖中可以觀察到一個規律**每往下推進一行，左邊的攻擊便會左移一格，右邊的攻擊便會右移一格，垂直的攻擊則不會移動**，在得到了這個想法之後，不妨將上面那張圖轉成以下三個部分

Left Attack
i   | 0 0 0 0 Q 0 0 0
i+1 | 0 0 0 X 0 0 0 0
i+2 | 0 0 X 0 0 0 0 0

Right Attack
i   | 0 0 0 0 Q 0 0 0
i+1 | 0 0 0 0 0 X 0 0
i+2 | 0 0 0 0 0 0 X 0

Vertical Attack
i   | 0 0 0 0 Q 0 0 0
i+1 | 0 0 0 0 X 0 0 0
i+2 | 0 0 0 0 X 0 0 0

做到這邊，有一個熟悉的東西就呼之欲出了，對 就是**位元運算**，我們可以透過位元運算的左移跟右移運算子達到攻擊轉換的目的，同時利用 OR 跟 AND 完成新增跟查詢攻擊

## **完整程式**

這裡比較值得注意的部分就是如何查詢跟改變特定位置的位元

* 如果想要把 X 位置的位元改變成 True 的話可以這樣做 ➨ `Variable | ( 1 << X )`

* 如果是要查詢的話可以這樣寫 ➨ `Variable & ( 1 << X )` 當你查詢的那一格是 True 的話就會回傳 True 反之回傳 False

* 如果是要左移整個變數一格的話可以簡寫成 ➨ `Variable <<= 1`，右移的話可以簡寫成 ➨ `Variable >>= 1`

/* Question : CSES 1624. Chessboard and Queens */

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

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mem(x) memset(x, 0x3F, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define f first
#define s second

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 8 + 50;
const int Mod = 1e9 + 7;
char grid[MAXN][MAXN];
int res;

void sol( int n, int l, int r, int v ){
    if( n == 9 ){
        res++;
        return;
    }

    l <<= 1;
    r >>= 1;
    for( int i = 0 ; i < 8 ; i++ ){
        if( l & ( 1 << i ) ) continue;
        if( r & ( 1 << i ) ) continue;
        if( v & ( 1 << i ) ) continue;
        if( grid[n-1][i] == '*' ) continue;

        sol( n + 1, l | ( 1 << i ), r | ( 1 << i ), v | ( 1 << i ) );
    }
}

signed main(){
    opt;
    for( int i = 0 ; i < 8 ; i++ ){
        for( int j = 0 ; j < 8 ; j++ ) cin >> grid[i][j];
    }
    sol(1, 0, 0, 0);
    cout << res;
}