3346. 皇后问题

单点时限: 2.0 sec

内存限制: 256 MB

八皇后问题是一个以国际象棋为背景的问题:如何能够在 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。

八皇后问题可以推广为更一般的 皇后摆放问题:这时棋盘的大小变为 ,而皇后个数也变成

现在给你 个皇后的位置座标,问总共有多少对皇后互相冲突。

输入格式

第一行一个整数 ,表示有 个皇后。

接下来 行,每行两个整数 ,中间用空格分开,表示 个皇后的坐标。

数据保证不会有两个皇后在同一个地方。

数据规模约定:

  • 对于 的数据,
  • 对于 的数据,

输出格式

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

样例

Input
3
1 1
1 2
1 3
Output
3
Input
2
1 1
2 2
Output
1
Input
4
1 3
2 1
3 4
4 2
Output
0

338 人解决,468 人已尝试。

521 份提交通过,共有 2747 份提交。

2.9 EMB 奖励。

创建: 2 年,2 月前.

修改: 2 年,1 月前.

最后提交: 4 天,11 小时前.

来源: 2017 直升研究生机试

题目标签