PAT甲级1128.

目录

A1128

题目

样例

输入:

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

思路和坑点

　　思路：
　　根据题目的描述，判定是否同一行、同一列或者对角线（行列坐标差值相等），由于题目按照每列的顺序给出，所以已经满足不同列的要求，只需判断另外两个条件即可。

AC代码

#include<bits/stdc++.h>
using namespace std; 
typedef struct node{                    //表示每个棋子的坐标
    int x,y;
}Node;
void Judge();
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)                //依次判断n个序列
        Judge();
    return 0;    
}
void Judge()
{
    int n;
    scanf("%d",&n);
    vector<Node> v;
    for(int i=1;i<=n;i++){
        Node temp;
        temp.y=i;                       //表示列
        scanf("%d",&temp.x);            //表示行
        v.push_back(temp);              //读入节点
    }
    bool flag=true;
    for(int i=0;i<n;i++){               //两两进行判定
        for(int j=i+1;j<n;j++){         
            if(v[i].x==v[j].x||v[i].x-v[j].x==v[i].y-v[j].y){
                flag=false; break;      //因为已知不再同一列，所以只需要判断是否再同一列或者是否对角线（横竖坐标差值相同）
            }                           //如果同行或者同对角线，则判定为否
        }
        if(flag==false)                 //判断标记，可以提前退出双重循环
            break;
    }
    puts(flag?"YES":"NO");
}