PAT a1128

目的:判断是不是Queens  Puzzle

输入：

K  例子个数，[1 200]

N  图片大小，[4  1000]

输出：

是的输出，YES

不是输出，NO

算法：

 不在一行好判断，不在一条斜线上，在一条斜线上的两个点，要不行列的和相等，要不行列的差相等。

#include<stdio.h>
#include<algorithm>

using namespace std;

const int maxn = 1010;

int r[maxn],d1[maxn],d2[maxn];
int K,N;

int main()
{
    scanf("%d",&K);

    for(int i=0;i<K;i++)
    {
        scanf("%d",&N);
        for(int j=1;j<=N;j++)
        {
            int c;
            scanf("%d",&c);
            r[j] = c;
            d1[j] = c + j;
            d2[j] = c - j;
        }
        sort(r+1,r+N+1);
        sort(d1+1,d1+N+1);
        sort(d2+1,d2+N+1);
        int flag = 0;
        for(int j=1;j<N;j++)
        {
            if(r[j]==r[j+1]||d1[j]==d1[j+1]||d2[j]==d2[j+1])
            {
                printf("NO\n");
                flag = 1;
                break;
            }
        }
        if(flag==0)
        printf("YES\n");
    }
    return 0;
}

反思：

其实可以用两点比较，相当于一个三角形，两点的行距和列距相等，就在一条斜线上。