Description
众所周知QWQ的棋艺已经到了独孤求败的地步，某日一位来自泰坦星的勇士前来向QWQ发起挑战，不过挑战的项目却非常奇怪：这位勇士要求QWQ在一个n x n大小的棋盘上放置k个棋子，并要求放置后的棋盘上每一行和每一列最多有一个棋子，显然这个问题是如此的简单，所以这位勇士要求QWQ告诉他这样的棋局共有多少种？ 你能帮助QWQ解决这个问题么？
Input
每组输入占据一行 一行有两个数字 分别表示棋盘的大小n和要求放置的棋子k 0<n<9 , 0<k<=n
Output
每组输入占据一行 输出这样的棋局的种类数目
Accepted Code
#include <bits/stdc++.h>
using namespace std;
int n,k,cnt=0;
int a[15]={0};
int num[15]={0,1,2,3,4,5,6,7,8,9,10};
void dfs(int cur)
{
if(cur==k+1)
{
++cnt;
return;
}
else
{
for (int i = 1; i <= n; i++)
{
if(num[i]!=0)
{
a[cur]=num[i];
num[i]=0;
dfs(cur+1);
a[cur]=0;
num[i]=i;
}
}
}
}
long long jiecheng[13] = {0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600};
long long zuheshu(int a, int b)
{
if(a==b||a==0)
return 1;
else
return (jiecheng[b] / (jiecheng[b - a]*jiecheng[a]));
}
int main()
{
cin>>n>>k;
dfs(1);
cout<<cnt*zuheshu(n-k,n)<<endl;
return 0;
}解后反思
本题发源于深度优先搜索典型题——八皇后，这里完全可以当做八皇后来做之后乘上一个0位出现的可能情况即可