PAT甲题题解-1128. N Queens Puzzle (20)-做了一个假的n皇后问题

博主欢迎转载，但请给出本文链接，我尊重你，你尊重我，谢谢~
http://www.cnblogs.com/chenxiwenruo/p/6789810.html
特别不喜欢那些随便转载别人的原创文章又不给出链接的
所以不准偷偷复制博主的博客噢~~

一开始以为是八皇后问题，这不就需要状态压缩dp嘛，PAT没想到竟然还会考这个
往后看才发现，原来只是判断是否是八皇后问题的一个解而已。

很明显，八皇后的一个解，每条行、列、对角线最多有1个皇后
所以for一遍的时候，相应行、列、对角线的个数++，如果有大于1的，那肯定就不是了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>using namespace std;
const int maxn=+;
int row[maxn];
int col[maxn];
int diagonal[maxn*]; //diagonal[i]表示第i条对角线上是否有queen
int n;
int main()
{
    int t;
    scanf("%d",&t);
    for(int i=;i<t;i++){
        scanf("%d",&n);
        memset(row,,sizeof(row));
        memset(col,,sizeof(col));
        memset(diagonal,,sizeof(diagonal));
        int r,c;
        bool flag=true;
        for(c=;c<=n;c++){
            scanf("%d",&r);
            r=n-r+;
            row[r]++;
            col[c]++;
            diagonal[r+c-]++;
            if(row[r]>)
                flag=false;
            if(col[r]>)
                flag=false;
            if(diagonal[r+c-]>)
                flag=false;
        }
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return ;
}