AcWing 1621. $\Huge\color{orange}{N}$$ \large\color{green}{皇后问题}$    原题链接    简单

作者： 作者的头像   Value ,  2020-05-22 11:28:09 ,  所有人可见 ,  阅读 2517

5


1

直接暴力(最后进行检查)

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 1010;
int loc[N];
bool check(int t){
    for(int i = 0; i < t; i ++ ){
        for(int j = 0; j < i; j ++ ){
            if(loc[i] == loc[j] || abs(loc[i] - loc[j]) == abs(i - j))  return false;
        }
    }
    return true;
}
int main(){
    int k, n;
    cin >> k;
    while(k -- ){
        scanf("%d", &n);
        for(int i = 0; i < n; i ++ )    scanf("%d", &loc[i]);
        if(check(n)) printf("YES\n");
        else    printf("NO\n");
    }
    return 0;
}

写法二（边输入边检查）

注意：此方法无论中途是否合法，都要把数据吃光（接收掉所以的输入）；否则会影响下一次的输入

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int a[N];
bool check(int x, int y){
    for(int i = 1; i < x; i ++ ){
        if(y == a[i] || abs(i - x) == abs(a[i] - y))    return false;
    }
    return true;
}
int main(){
    int k;  cin >> k;
    while(k -- ){
        int n;  cin >> n;
        bool flag = true;
        for(int i = 1; i <= n; i ++ ){
            int t;  cin >> t;
            if(!check(i, t))    flag = false;
            a[i] = t;
        }
        cout << (flag ? "YES" : "NO") << endl;
    }
    return 0;
}

6 评论

用户头像
学算法的女子汉   2023-04-07 12:51         踩      回复 
#include <bits/stdc++.h>
using namespace std;
int a[1100],n;

bool check(int x)
{
    for(int i=0;i<x;i++)
    {
        for(int j=0;j<x;j++)
        {
            if(a[i]==a[j] || abs(a[i]-a[j])==abs(i-j))  return false;
        }
    }
    return true;
}
int main()
{
    int k;
    cin >> k;
    while(k--)
    {
        cin >> n;
        for(int i=1;i<=n;i++)   cin>>a[i];
        if(check(n))    cout << "YES" << endl;
        else cout << "NO" <<endl;
    }
    return 0;
}
用户头像
学算法的女子汉   2023-04-07 12:51         踩      回复

求点拨呜呜呜，怎么输出都是NO啊😔

用户头像
Value   2023-04-07 15:59    回复了 学算法的女子汉 的评论         踩      回复

两个问题：
1. 你输入的时候a的小标从1开始，而你的check函数里面是从0开始的，需要统一
2. check函数的时候，每个点应该和其后面的顶点进行检查，而不是和所以的顶点进行检查（自己和自己进行判断，当然会返回false）；即判断点（1，a[1]）与2,3，…,n顶点是否冲突，第二次判断（2，a[2]）与3,4,5…n是否冲突，依次下去
以下是我对你的代码进行的修改之后的程序（已AC）：

#include <bits/stdc++.h>
using namespace std;
int a[1100],n;
bool check(int x)
{
    for(int i=1;i<=x;i++)
    {
        for(int j=i+1;j<=x;j++)
        {
            if(a[i]==a[j] || abs(a[i]-a[j])==abs(i-j)){
               return false;
            }  
        }
    }
    return true;
}
int main()
{
    int k;
    cin >> k;
    while(k--)
    {
        cin >> n;
        for(int i=1;i<=n;i++)   cin>>a[i];
        if(check(n))    cout << "YES" << endl;
        else cout << "NO" <<endl;
    }
    return 0;
}
用户头像
青丝蛊   2021-01-23 18:45         踩      回复

abs(loc[i] - loc[j]) == abs(i - j) 为啥列差和行差相等就不行呀，这是怎么体现在对角线上的

用户头像
卧牛   2021-01-30 20:22      1    踩      回复

斜率绝对值为1

用户头像
Everythingisok_9   2022-04-01 20:01    回复了 卧牛 的评论         踩      回复

妙啊