皇后问题判断冲突(一）

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

来源EOJ，ECNU Online Judge

本文采用傻瓜做法，仅通过1≤n≤100的情况。

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

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

代码

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

思路，先建一个二维数组，初始化为0。依次读入皇后的位置，在数组中用1标记。然后对于数组中的每一个格子，查看他的上下左右以及四个对角线方向有没有其他皇后，有则冲突++。cf记录冲突总数，最后除以二因为a与b冲突和b与a冲突会被记做两次。这种做法复杂度极高，很不妙，但1≤n≤100我觉得很行。

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int t=n;
    int m[n+1][n+1] {0};
    while(t--)
    {
        int x,y;
        cin>>x>>y;
        m[x][y]=1;
    }
    long long cf=0;//记录冲突总数,a与b冲突和b与a冲突会被记做两次
    int i,j,ii,jj;

    for (i=1; i<=n; i++)
    {
        for (j=1; j<=n; j++)
        {
            //定位到ij，判断ij与哪些有冲突
            if(m[i][j]==1) //0不用算
            {
                for (ii=1; ii<=n; ii++)
                {
                    if (m[ii][j]==1 && ii!=i)cf++;
                }
                for (jj=1; jj<=n; jj++)
                {
                    if (m[i][jj]==1 && jj!=j)cf++;
                }
                for (ii=i,jj=j; ii>=1 && jj>=1; ii--,jj--)
                {
                    //左上
                    if (m[ii][jj]==1 & (ii!=i || jj!=j))cf++;
                }
                for (ii=i,jj=j; ii<=n && jj<=n; ii++,jj++)
                {
                    //右下
                    if (m[ii][jj]==1 & (ii!=i || jj!=j))cf++;
                }
                for (ii=i,jj=j; ii>=1 && jj<=n; ii--,jj++)
                {
                    //右上
                    if (m[ii][jj]==1 & (ii!=i || jj!=j))cf++;
                }
                for (ii=i,jj=j; ii<=n && jj>=1; ii++,jj--)
                {
                    //左下
                    if (m[ii][jj]==1 & (ii!=i || jj!=j))cf++;
                }

            }
        }
    }
    cout<<cf/2<<endl;
}