还是皇后问题,现在需要你求出一共有多少种可能的摆放,并且输出任意一种摆放
在求摆放方案数的基础上,增加了输出摆放的要求。
输入格式
只有 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]<<" ";
}
}
}