题目描述

N皇后问题是指将 N个皇后放置在N×N棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
在本题中，你无需解决这一难题。
你需要做的是判断我们给出的棋子摆放是否是一种合理的摆放方案，即是否能够满足皇后之间不能相互攻击到。
为了简化棋盘的表示，让我们假设在同一列中不会放置两个皇后。
这样我们就可以用一个整数序列 Q1,Q2,…,QN来表示一种棋盘摆放，其中 Qi表示第i列的皇后所在的行号。
输入格式
第一行包含整数 K，表示共有 K组测试数据。
每组测试数据占一行，首先包含整数 N，然后包含 N个整数 Q1,Q2,…,QN。
输出格式对于每组数据，如果是合理摆放方案，则输出 YES，否则输出 NO。
每个答案占一行。

样例

输入样例：
4
8 4 6 8 2 7 1 3 5
9 4 6 7 2 8 1 9 5 3
6 1 5 2 6 4 3
5 1 3 5 2 4
输出样例：
YES
NO
NO
YES

算法1

(暴力枚举)

每一组数据边输入边除去不合法的位置,而且一边检测当皇后放在该行该列的位置是否合法,
当找到第一个不合法的位置就可以输出NO 

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n;
int zhu[2001],fu[2001],c[1001];
int main(){
    int t; cin >> t;
    while(t--){
        memset(zhu,0,sizeof zhu); memset(fu,0,sizeof fu); memset(c,0,sizeof c);
        cin >> n; 
        bool flag = true;
        for(int i = 1; i <= n; i++){
            int x; cin >> x;
            if(!flag) continue;
            if(c[x] || fu[i + x] || zhu[i - x + n]) {
                cout << "NO" << endl; 
                 flag = false; 
            }
            if(flag)
            c[x] = fu[i + x] = zhu[i - x + n] = 1;
        }
        if(flag)
        cout << "YES" << endl;

    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla