2020年12月28日

皇后问题判断冲突(一)

作者 admin

八皇后问题是一个以国际象棋为背景的问题:如何能够在 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;
}