[CSES] Chessboard and queens

Đề bài

Nhiệm vụ của bạn là đếm số cách sắp xếp 8 quân hậu trên bàn cờ 8*8, sao cho không có hai quân hậu nào có thể tấn công nhau. Để cho bài toán thêm thú vị, sẽ có một vài vị trí mà không thể đặt quân hậu tuy nhiên những vị trí này không thể ngăn cản những con hậu tấn công nhau.

Yêu cầu:

• Gồm 8 dòng , mỗi dòng có 8 kí tự. Kí từ ‘.’ biểu thị vị trí có thể đặt hậu, ‘*’ biểu thị vị trí không thể đặt hậu.

Kết quả:

• In ra một số nguyên, số cách có thể đặt 8 quân hậu đáp ứng yêu cầu của bài toán.

Ví dụ:

Hướng dẫn

• Đầu tiên ta sẽ đặt bảng của ta là bảng $S$ với kí tự ở ô $i,j$ là $S_{i,j}$.
• Ta có một lời giải được cho là hợp lệ thì ta phải có $S_{1,i_1},S_{2,i_2},….S_{n,i_n}$.
  • Với $i_1,i_2,i_3,…i_n$ lập thành một hoán vị từ $1 \to n$.
  • Không có 2 quân hậu thuộc đường chéo phụ hay nói cách khác $1+i_1,2 + i_2,3+i_3,…,n+i_n$ đội một phân biệt.
  • Không có 2 quân hậu thuộc đường chéo chính hay nói cách khác $1-i_1,2 – i_2,3-i_3,…,n-i_n$ đội một phân biệt.
  • Không có quân hậu nào có $S_{i,j} = *$.
• Ở những bài tập trước chúng ta đã quá quen với việc sinh hoán vị từ $1 \to n$, để kiểm tra hai điều kiện sau chúng ta sẽ dùng một mảng để kiểm tra sự xuất hiện. Lưu ý khi kiểm tra đường chéo chính do có thể âm nên hãy nâng ảo lên một lượng là $7$ để không bị bug. Việc kiểm tra xem $S_{i,j} =*$ hay không là một bài toán cơ bản.

Mã nguồn tham khảo

#include <bits/stdc++.h>
using namespace std;
#define task "test"
const int N = 1e5+1;
typedef pair<int,int> pi;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
string s[8];
void solve(){
 
   for(int i=0;i<8;i++) cin >> s[i];
 
   vector<int>col(8);
 
   iota(col.begin(),col.end(),0);
   int ans = 0;
   bool check[15];
 
   do{
       int ok = 1;
       for(int i=0;i<8;i++){
           if(s[i][col[i]]=='*') {
             ok =0;
             break;
           }
       }
       for(int i=0;i<15;i++) check[i]=0;
       // check duong cheo phu
       for(int i=0;i<8;i++){
           if(check[i+col[i]]) ok = 0;
           check[i+col[i]]=1;
       }
 
        for(int i=0;i<15;i++) check[i]=0;
       // check duong cheo chinh
       // do phep tru nen co truong hop se bi am vi the ta se +7 de no thanh duong
       for(int i=0;i<8;i++){
           if(check[i-col[i]+7]) ok = 0;
           check[i+7-col[i]]=1;
       }
 
 
       ans+=ok;
 
 
   }while(next_permutation(col.begin(),col.end()));
 
   cout << ans;
 
 
 
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    int t;
    t=1;
    while(t-->0){
        solve();
    }
 
}