A116897.小午历险记之蜂巢信标

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

在一片无限延伸的蜂巢状区域中,所有的六边形单元最初都是未激活状态。每一个六边形单元可以用一对整数坐标 (i,j)(i, j) 表示为 (i,j)(i, j)
在这种蜂巢网格中,单元 (i,j)(i, j) 与下面 6 个 单元直接相邻:

  • (i1,j1)(i-1, j-1)
  • (i1,j)(i-1, j)
  • (i,j1)(i, j-1)
  • (i,j+1)(i, j+1)
  • (i+1,j)(i+1, j)
  • (i+1,j+1)(i+1, j+1)

现在,小午在其中的 NN 个单元上放置了信标,这些被放置信标的单元视为激活状态,其坐标分别为 (X1,Y1),(X2,Y2),,(XN,YN)(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)

如果两个激活的单元之间,可以通过若干步每一步都移动到相邻的激活单元互相到达,那么它们属于同一个信标网络。

请找出这些激活的单元一共形成了多少个互不连通的信标网络。

输入格式

第一行一个整数 NN

接下来 NN 行,每行两个整数 Xi,YiX_i, Y_i,表示一个被激活的蜂巢单元坐标。

输出格式

输出一个整数,表示信标网络的数量。

输入输出样例

  • 输入#1

    6
    -1 -1
    0 1
    0 2
    1 0
    1 2
    2 0

    输出#1

    3

说明/提示

样例解释

被激活的蜂巢单元可以按照相邻关系分成以下 33 个信标网络:

  • 单独的单元 (1,1)(-1,-1)
  • 相互连通的单元 (1,0)(1,0)(2,0)(2,0)
  • 相互连通的单元 (0,1),(0,2),(1,2)(0,1),(0,2),(1,2)

它们之间两两无法通过相邻激活单元互相到达,因此形成了 33 个独立的连通块。

数据范围

对于 100%100\% 的测试数据,满足:1N10001 \le N \le 1000 , 所有坐标 (Xi,Yi)(X_i, Y_i) 两两不同, 坐标范围在有限区域内,但蜂巢网格本身视为无限大

首页