AcWing 1621. N 皇后问题
原题链接
简单
作者:
eveer
,
2021-08-27 11:51:45
,
所有人可见
,
阅读 199
/*
需要创建3个数组来判断当前的行,对角线以及斜对角线上是否已经有元素了
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2010;//题目要求中最多只有1000*1000的矩阵,也就意味着有2*1000多条对角线,因此N要开到2010
int q[N];
bool row[N];//row[i]判断第i行是否已经占有元素
bool diag[N];//diag[i]判断第i根对角线上是否已经占有元素,其中,i=n-(row-column),column表示列号,row表示行号
bool bdiag[N];//bdiag[i]判断第i根反对角线上是否已经占有元素,其中,i=row+column-1
bool is_answer(int k,int q[])//判断当前是否为一个合法解
{
memset(row,false,sizeof row);//初始化为false表示每一个位置都可以放
memset(diag,false,sizeof diag);
memset(bdiag,false,sizeof bdiag);
for(int i=1;i<=k;i++)//i是当前的列号
{
int num=q[i];//num表示第i列所放元素的行号
//printf("%d ",num);
if(row[num]==true || diag[k-num+i]==true || bdiag[num+i-1]==true)
return false;
else
{
row[num]=true;diag[k-num+i]=true; bdiag[num+i-1]=true;//表示当前的行,对角线上已经占有了元素
}
}
return true;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int k;
scanf("%d",&k);//k表示皇后的数量
for(int i=1;i<=k;i++)scanf("%d",&q[i]);//记录每一列上皇后所在的位置
bool flag=is_answer(k,q);
if(flag==true)printf("YES\n");
else printf("NO\n");
}
return 0;
}