本文共 1465 字，大约阅读时间需要 4 分钟。

题目链接：

题目描述

kotori最近在研究n皇后的问题。

所谓n皇后问题是这样的：一个n*n的地图，上面一共放n个皇后，保证任意两个皇后都不能互相攻击（每个皇后可以攻击同一行、同一列以及同一45度角斜线和135度角斜线上的所有其他皇后）。

kotori思考了很久都无法得出答案，整个人都变成琴梨了。她于是拿了一堆皇后在一个无穷大的棋盘上模拟，按照次序一共放了k个皇后。

但是，皇后的站位太复杂了，kotori甚至不知道是否存在两个皇后会互相攻击。于是她想问问聪明的你，在第i个皇后放置在棋盘上之后，是否存在两个皇后可以互相攻击？

输入描述

第一行输入一个正整数k，代表总共放置的皇后的个数。（1<=k<=1e5）

输出描述

共t行。每行对应当前的询问是否存在两个皇后可以互相攻击，若是则输出“Yes”，否则输出“No”

输入

5

1 2

2 5

3 1

6 7

4 8

2

2

4

输出

No

Yes

说明

第四个皇后放置后，第四个和第一个皇后可以互相攻击。

解题思路

题意:判断是否存在两个皇后可以互相攻击。

Accepted Code:

#include 
   
    using namespace std;const int inf = 0x3f3f3f3f;set 
    
      setr, setc, set45, set135;bool Judge(int x, int y) {    if (setr.count(x) || setc.count(y) || set45.count(x - y) || set135.count(x + y))        return true;    return false;}int main() {    int n, m, t, x, y, min_ = inf;    scanf("%d", &n);    for (int i = 1; i <= n; i++) {        scanf("%d%d", &x, &y);        if (min_ >= inf) {            if (Judge(x, y))                min_ = i;            setr.insert(x);            setc.insert(y);            set45.insert(x - y);            set135.insert(x + y);        }    }    scanf("%d", &t);    while (t--) {        scanf("%d", &m);        if (m >= min_)            printf("Yes\n");        else printf("No\n");    }    return 0;}
    
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/94551301 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！