计算 n*n 棋盘中摆放 n 个皇后的方案数
来源EOJ,ECNU Online Judge
输入格式:第一行有一个整数 k,表示有 k 个 case,接下来 2..k+1 行,每行有一整数,表示 n*n 的棋盘 (0 < n <= 8)。
输出格式:输出共有 k 行,每行有一个整数,即 n*n 的摆放皇后的方案数
代码
声明,该代码本人书写,不排除有错的可能,但大多数时候应该是对的。
思路:判断冲突方法可参考这篇文章
success表示方案数。
思路是每行每行的找。第0行,遍历每一列,如果该列可以放东西则标记为1,继续next(下一行),然后再标记回0,继续下一列。
如果执行到第n行,则是一次成功的方案,success++。
#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;
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)
{
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()
{
int ca;
cin>>ca;
while(ca--)
{
success=0;
cin>>n;
for (int p=0; p<20; p++)
row[p]=0;
for (int p=0; p<40; p++)
{
r_c[p]=0;
rPLUSc[p] =0;
}
next(0);
cout<<success<<endl;
}
}