A116897.小午历险记之蜂巢信标
普及/提高-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
在一片无限延伸的蜂巢状区域中,所有的六边形单元最初都是未激活状态。每一个六边形单元可以用一对整数坐标 (i,j) 表示为 (i,j)。
在这种蜂巢网格中,单元 (i,j) 与下面 6 个 单元直接相邻:
- (i−1,j−1)
- (i−1,j)
- (i,j−1)
- (i,j+1)
- (i+1,j)
- (i+1,j+1)
现在,小午在其中的 N 个单元上放置了信标,这些被放置信标的单元视为激活状态,其坐标分别为 (X1,Y1),(X2,Y2),…,(XN,YN)
如果两个激活的单元之间,可以通过若干步每一步都移动到相邻的激活单元互相到达,那么它们属于同一个信标网络。
请找出这些激活的单元一共形成了多少个互不连通的信标网络。
输入格式
第一行一个整数 N。
接下来 N 行,每行两个整数 Xi,Yi,表示一个被激活的蜂巢单元坐标。
输出格式
输出一个整数,表示信标网络的数量。
输入输出样例
输入#1
6 -1 -1 0 1 0 2 1 0 1 2 2 0
输出#1
3
说明/提示
样例解释
被激活的蜂巢单元可以按照相邻关系分成以下 3 个信标网络:
- 单独的单元 (−1,−1)
- 相互连通的单元 (1,0) 与 (2,0)
- 相互连通的单元 (0,1),(0,2),(1,2)
它们之间两两无法通过相邻激活单元互相到达,因此形成了 3 个独立的连通块。
数据范围
对于 100% 的测试数据,满足:1≤N≤1000 , 所有坐标 (Xi,Yi) 两两不同, 坐标范围在有限区域内,但蜂巢网格本身视为无限大