首页 > 试题广场 >

皇后大战

[编程题]皇后大战
在一个无限大的棋盘上,安放皇后。每个皇后可以攻击到其所在位置的行、列以及两条对角线上的皇后。
现在要将这些皇后划分阵营,共两种阵营。规定同一阵营的皇后不会互相攻击,不同阵营的皇后之间可以进行互相攻击。
现在要将皇后划分阵营,要求所有皇后之间不能互相攻击,且一个阵营最少要有一个皇后,求有多少种不同的划分方法。

输入描述:
第一行输入一个整数 N,表示皇后的总数。
接下来 N 行,每行输入两个整数 x, y,表示一个皇后的坐标。

数据范围:
1 \le N < 100000
-10^9 \le x, y \le 10^9
所有坐标互不相同。


输出描述:
输出一个整数,表示划分方法数。
示例1

输入

4
1 1
2 3
3 2
4 4

输出

4
示例看不懂,为什么输出4?

发表于 2026-01-11 17:33:58 回复(0)