2020年12月29日

皇后问题判断冲突(二)

作者 admin

八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。推广为更一般的 n 皇后摆放问题:这时棋盘的大小变为 n×n,而皇后个数也变成 n。现在给你 n 个皇后的位置座标,问总共有多少对皇后互相冲突。

来源EOJ,ECNU Online Judge

本文是一种AC做法,用二维数组存储的方法见皇后问题判断冲突(一)


输入第一行一个整数 n,表示有 n 个皇后。接下来 n 行,每行两个整数 x,y ,(1≤x,y≤n),中间用空格分开,表示 n 个皇后的坐标。数据保证不会有两个皇后在同一个地方。数据规模约定:1≤n≤105

输出一个整数,表示有多少对皇后互相冲突。


代码

声明,该代码本人书写,不排除有错的可能,但大多数时候应该是对的。

思路:用四个一维数组分别存储行row、列column、主对角线r_c、次对角线上rPLUSc的皇后数量。例如(1,1)(1,2)(1,3)位置上有皇后,则第一行row[1]的值记为3。最后,求各行各列各对角线上的组合数之和Cx2

tips,主对角线方向上的元素行号减列号的值恒定(差可能为负,可以都加上n来调节);次对角线方向,行号与列好之和恒定。

#include <iostream>

using namespace std;

long long C(int n,int m)
{
    
    if(m==n||m==0)
        return 1;
    if(m==1)return n;
//优化,不然易超时
    return(C(n-1,m-1)+C(n-1,m));
}

int main()
{
    int n;
    cin>>n;
    int t=n;
    int row[n+1] {0};
    int column[n+1] {0};
    int r_c[2*n+1] {0}; //主对角线
方向
    int rPLUSc[2*n+1] {0}; //次对角线
方向
    int x,y;
    while(t--)
    {
        cin>>x>>y;
        row[x]++;
        column[y]++;
        r_c[x-y+n]++;
        rPLUSc[x+y]++;
    }
    long long sum=0;
    int k;
    for (k=0; k<n+1; k++)
    {
        if (row[k]>1)sum+=C(row[k],2);
    }
    for (k=0; k<n+1; k++)
    {
        if (column[k]>1)sum+=C(column[k],2);
    }
    for (k=0; k<2*n+1; k++)
    {
        if (r_c[k]>1)sum+=C(r_c[k],2);
    }
    for (int k=0; k<2*n+1; k++)
    {
        if (rPLUSc[k]>1)sum+=C(rPLUSc[k],2);
    }
    cout<<sum<<endl;
    return 0;
}