文章

受伤的皇后(2021模拟赛)

受伤的皇后1.png

突然想到的用全排列 一维数组全部初始化为a[i]=i,这样可以保证前两个条件一定成立 一维数组的下标表示行,a[i]表示第i行的第a[i]列有皇后 所以只需要验证45度角的条件是否满足即可

#include<bits/stdc++.h>
using namespace std;
int sum=0,n;
int a[20];
int select(){
    int i;
    for(i=1;i<=n;i++){
        if(i-1<1|| (i-1>=1&&a[i]-a[i-1]!=-1&&a[i]-a[i-1]!=1) ){ }else return 0;
        if(i-2<1|| (i-2>=1&&a[i]-a[i-2]!=-2&&a[i]-a[i-2]!=2) ){ }else return 0;
    }
    return 1;
}
void swap(int x,int y){
    int t=a[x];
    a[x]=a[y];
    a[y]=t;
    return ;
}
void perm(int key){
    if(key==n+1) sum+=select();
    for(int i=key;i<=n;i++){
        swap(i,key);
        perm(key+1);
        swap(i,key);
    }
    return ;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)  a[i]=i;
    perm(1);
    cout<<sum<<endl;
    return 0;
}

原题链接

https://www.lanqiao.cn/problems/552/learning/

License:  CC BY 4.0