在一个无限大的棋盘上,安放皇后。每个皇后可以攻击到其所在位置的行、列以及两条对角线上的皇后。
现在要将这些皇后划分阵营,共两种阵营。规定同一阵营的皇后不会互相攻击,不同阵营的皇后之间可以进行互相攻击。
现在要将皇后划分阵营,要求所有皇后之间不能互相攻击,且一个阵营最少要有一个皇后,求有多少种不同的划分方法。
第一行输入一个整数,表示皇后的总数。
接下来行,每行输入两个整数
,表示一个皇后的坐标。
数据范围:
所有坐标互不相同。
输出一个整数,表示划分方法数。
4 1 1 2 3 3 2 4 4
4