思路
判断主副对角线就是看x, y之间的关系。
先开数组,每次读入一个数就看他的行,主,副对角线是否被标记过了,若有,则是非法方案。
注
所有下标从1 开始
时间复杂度
每个皇后只遍历一遍$O(n)$, 一共有200组测试数据,N = 1000,总的为2e5
图上正反对角线写反了!
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
bool row[N], dg[2*N], udg[2*N]; //主副对角线的数组范围为2倍
int main()
{
int q;
cin >> q;
while (q--)
{
int n;
cin >> n;
//多组输入,记得初始化
memset(row, 0, sizeof row);
memset(dg, 0, sizeof dg);
memset(udg, 0, sizeof udg);
bool success = true;
for (int y = 1; y <= n; y++) //y:列
{
int x; //x: 行
cin >> x;
if (row[x] || dg[y-x+n] || udg[x+y]) //若前面有输入了
success = false; //这里不能提前break掉,要把输完
row[x] = dg[y-x+n] = udg[x+y] = true;
}
if (success) puts("YES");
else puts("NO");
}