皇后问题判断冲突(二）

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

来源EOJ，ECNU Online Judge

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

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

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

代码

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

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

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;
}