UVa

UVa00750 UvaLive5358 8 Queens Chess Problem

題目連結 UVa
題目連結 UvaLive

  • 題意：給定八皇后問題其中一顆棋子，求所有可能的八皇后問題解。
  • 題解：經典八皇后問題，遞迴到已經放過棋子的那一層就直接跳過。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #include <iostream>
    #include <cstring>
    using namespace std;
    int vis[20][20],cur[20],x,y,c;//0 x 1 \ 2 / c:caculate

    void dfs(int n){
        if(n==9){
            if(c/10==0)cout<<' ';
            cout<<c++<<"     ";
            for(int i=1;i<=8;i++){
                cout<<' '<<cur[i];
            }
            cout<<'\n';
            return;
        }if(n==y){
            dfs(n+1);
        }else{
            for(int i=1;i<=8;i++){
                if(!vis[0][i]&&!vis[1][i-n+8]&&!vis[2][i+n]){
                    cur[n]=i;
                    vis[0][i]=vis[1][i-n+8]=vis[2][i+n]=1;
                    dfs(n+1);
                    vis[0][i]=vis[1][i-n+8]=vis[2][i+n]=0;
                }
            }
        }
        return;
    }

    int main(){
        int n;
        for(cin>>n;n;n--){
            cin>>x>>y;
            memset(vis,0,sizeof(vis));
            c=1;
            vis[0][x]=vis[1][x-y+8]=vis[2][x+y]=1;
            cur[y]=x;
            cout<<"SOLN       COLUMN\n #      1 2 3 4 5 6 7 8\n\n";
            dfs(1);
            if(n>1)cout<<'\n';
        }
    }

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts