PAT(Advanced Level)A1128. N Queens Puzzle

题意

判断给出的放置方式是否符合N皇后棋盘的要求（也就是说每一行，每一列，每条对角线都不能冲突）

思路

• 棋子的位置是由每一列的第几个位置来给出的，所以列这个方向上实际上是不会冲突的
  • 行方向：用一个row数组
  • 主对角线方向：对于任意一个坐标(i, j)，同个主对角线的i - j为定值，同时要注意有可能有负数，所以应该加个偏移（我这里取最大的QN也就是1000）才不会数组越界
  • 副对角线方向：对于任意一个坐标(i, j)，同个主对角线的i + j为定值

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <set>
#include <string.h>
using namespace std;
bool row[1010], diag1[3000], diag2[3000];   // 分别判断行方向，主对角线方向，副对角线方向
int main() {
    int K, N, t;
    scanf("%d", &K);
    for(int i = 0; i < K; i++) {
        memset(row, 0, sizeof(row));
        memset(diag1, 0, sizeof(diag1));
        memset(diag2, 0, sizeof(diag2));
        scanf("%d", &N);
        bool illegal = false;
        for(int j = 0; j < N; j++) {
            scanf("%d", &t);
            t--;
            if(row[t] || diag1[j - t + 1000] || diag2[j + t]) {    // 行方向, 主对角线，副对角线冲突了
                illegal = true;
            }
            // 打上标记
            row[t] = true, diag1[j - t + 1000] = true, diag2[j + t] = true;
        }
        if(!illegal)
            cout << "YES
";
        else
            cout << "NO
";
    }
}