AcWing 1621. N 皇后问题
原题链接
简单
- 重点在于利用如何判断行、对角线、反对角线上没有两个及以上的皇后
- 判断条件
col[j] || dg[i + j] || udg[n + i - j]
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 3000;
bool col[N], dg[N], udg[N];
int a[N];
int main() {
int T;
cin >> T;
while (T--) {
memset(col, 0, sizeof col);
memset(dg, 0, sizeof dg);
memset(udg, 0, sizeof udg);
int n;
cin >> n;
for(int i = 0; i < n; i++) {
int x;
cin >> x;
a[i] = x - 1;
}
// 计算
bool flag = true;
for (int i = 0; i < n; i++) {
int j = a[i];
if (col[j] || dg[i + j] || udg[n + i - j]) {
flag = false;
break;
} else {
col[j] = dg[i + j] = udg[n + i - j] = true;
}
}
if (flag) puts("YES");
else puts("NO");
}
return 0;
}