【acwing 寒假每日一題（入門組）】day14 棋盤挑戰

題目來源：棋盤挑戰

題目描述

給定一個 N×N 的棋盤，請你在上面放置 N 個棋子，要求滿足：

1. 每行每列都恰好有一個棋子
2. 每條對角線上都最多隻能有一個棋子

1   2   3   4   5   6
  -------------------------
1 |   | O |   |   |   |   |
  -------------------------
2 |   |   |   | O |   |   |
  -------------------------
3 |   |   |   |   |   | O |
  -------------------------
4 | O |   |   |   |   |   |
  -------------------------
5 |   |   | O |   |   |   |
  -------------------------
6 |   |   |   |   | O |   |
  -------------------------
           

上圖給出了當 N=6 時的一種解決方案，該方案可用序列 2 4 6 1 3 5 來描述，該序列按順序給出了從第一行到第六行，每一行擺放的棋子所在的列的位置。

請你編寫一個程式，給定一個 N×N 的棋盤以及 N 個棋子，請你找出所有滿足上述條件的棋子放置方案。

輸入格式

共一行，一個整數 N。

輸出格式

共四行，前三行每行輸出一個整數序列，用來描述一種可行放置方案，序列中的第 i 個數表示第 i 行的棋子應該擺放的列的位置。

這三行描述的方案應該是整數序列字典序排在第一、第二、第三的方案。

第四行輸出一個整數，表示可行放置方案的總數。

資料範圍

6≤N≤13

輸入樣例：

6

輸出樣例：

2 4 6 1 3 5

3 6 2 5 1 4

4 1 5 2 6 3

4

思路

這個經典的八皇後問題，兩種正常思路

1. 一個格子一個格子枚舉，看看能不能放皇後
2. 一行一行枚舉，看看皇後放那一列

代碼

一個一個枚舉

#include<bits/stdc++.h>

using namespace std;


const int N=30; //開了兩倍 因為要存兩個對角線 對角線的個數是 2n-1 友善起見就開了兩倍多
int n;
bool row[N],col[N],dg[N],udg[N];
int path[N],ans;

/*
        按行枚舉 dg是主對角線 udg是反對角線
        主對角線是 y=-x+b 是以b是y+x  
        反對角線是y=x+b  b是y-x可能會是會負的 是以加一個n的偏移 
*/

void dfs(int x,int y,int s)
{
    if(y==n+1) x++,y=1;
    if(x==n+1)
    {
        if(s==n)
        {
            ans++;
            if(ans<=3)
            {
                for(int i=1;i<=n;i++) cout<<path[i]<<' ';
                cout<<endl;
            }
        }
        return;
    }
    dfs(x,y+1,s);
    if(!row[x] && !col[y] && !dg[x+y] && !udg[y-x+n])
    {
        int tmp=path[x];
        row[x]=col[y]=dg[x+y]=udg[y-x+n]=true;
        path[x]=y;
        dfs(x,y+1,s+1);
        row[x]=col[y]=dg[x+y]=udg[y-x+n]=false;
        path[x]=tmp;
    }
}

int main()
{
    cin>>n;
    dfs(1,1,0);
    cout<<ans<<endl;
    return 0;
}
           

按行枚舉

#include<bits/stdc++.h>

using namespace std;


const int N=30; //開了兩倍 因為要存兩個對角線 對角線的個數是 2n-1 友善起見就開了兩倍多
int n;
bool col[N],dg[N],udg[N];
int path[N],ans;

/*
        按行枚舉 dg是主對角線 udg是反對角線
        主對角線是 y=-x+b 是以b是y+x  
        反對角線是y=x+b  b是y-x可能會是會負的 是以加一個n的偏移 
*/

void dfs(int x)
{
    if(x>n)
    {
        ans++;
        if(ans<=3)
        {
            for(int i=1;i<=n;i++) cout<<path[i]<<' ';
            cout<<endl;
        }
        return;
    }
    for(int y=1;y<=n;y++)
    {
        if(!col[y] && !dg[x+y] && !udg[y-x+n])
        {
            path[x]=y;
            col[y]=dg[x+y]=udg[y-x+n]=true;
            dfs(x+1);
            path[x]=0;
            col[y]=dg[x+y]=udg[y-x+n]=false;
        }
    }
}

int main()
{
    cin>>n;
    dfs(1);
    cout<<ans<<endl;
    return 0;
}