皇后问题合集 · 2021年1月2日

皇后问题(SPJ)

还是皇后问题,现在需要你求出一共有多少种可能的摆放,并且输出任意一种摆放

在求摆放方案数的基础上,增加了输出摆放的要求。

输入格式

只有 1 行,为 1 个整数,表示 n×n 的皇后规模, 1⩽n⩽13

输出格式

输出一共 2 行

第一行是一个整数,表示一共有多少种可能的摆放

第二行输出任意一种可能的摆放,是 n 个数( x0,x1,⋯,xn−1 ),用空格分隔,分别表示第 i 行的皇后摆放在第 xi 列

行与列的下标从 0 开始,到 n−1

如果没有可能的摆放,那就只在第1行输出0,而不需要输出第2行

样例

input

4

output

2 1 3 0 2

提示

例如当输入n为4的时候,一共有2种摆放方式

这2种摆放分别为:

(0,1) (1,3) (2,0) (3,2)

(0,2) (1,0) (2,3) (3,1)

那么输出就可以是

2 1 3 0 2

也可以是

2 2 0 3 1

上代码

关键在红色一行,success等于0的时候会覆盖,一旦success不等于0就保持答案不再被更改。至于思路,可参考这篇文章

#include<bits/stdc++.h>
using namespace std;
int row[20] {0};
int r_c[40] {0};
int rPLUSc[40] {0};

int success=0;
int n;
int ans[20]{0};

void next(int nowrow)
{
    if (nowrow==n)
    {
        success++;
        return;
    }
    for (int col=0; col<n; col++)
    {
        if ( row[col]==0 && r_c[nowrow-col+n]==0 && rPLUSc[nowrow+col]==0)
        {
            if (!success)ans[nowrow]=col;

            row[col]=r_c[nowrow-col+n]=rPLUSc[nowrow+col]=1;
            next(nowrow+1);
            row[col]=r_c[nowrow-col+n]=rPLUSc[nowrow+col]=0;
        }
    }
}

int main()

{
    cin>>n;
    next(0);
    cout<<success<<endl;
    if (success)
    {
        for (int i=0;i<n;i++)
        {
            cout<<ans[i]<<" ";
        }
    }

}