NEFU-1606 QWQ和棋局挑战

NEFU-1606 QWQ和棋局挑战

/ 0评 / 1434次 / 0

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位出现的可能情况即可

发表回复

您的电子邮箱地址不会被公开。

你好 No.65347