SZ#G6DFS16. 【GESP强化 六级】黑色区域

提交1 通过1
通过率100%
时间限制2000ms
内存限制256MiB
    ID: 11472 传统题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 入门 上传者: 标签>GESPGESP强化C++c++编程题深度优先搜索坐标连通块GESP6级1星

题目描述

有一张无限大的六角格。每个格子用整数坐标 (i,j)(i,j) 表示,格子 (i,j)(i,j) 与下面六个格子相邻:

  • (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 个互不相同的格子涂成黑色,其余格子仍为白色。若两个黑格能通过若干次走到相邻黑格互相到达,就属于同一个黑色区域。请统计黑色区域数量。

输入格式

第一行输入 NN

接下来 NN 行输入黑格坐标 Xi,YiX_i,Y_i

输出格式

输出黑色连通区域数量。

4
0 1
30 30
0 0
30 31
2
5
0 1
30 30
60 60
0 2
30 31
3
6
0 1
30 30
60 60
90 91
0 0
30 31
4

数据范围与约定

  • 1N10001 \le N \le 1000
  • Xi,Yi1000|X_i|,|Y_i| \le 1000
  • 坐标两两不同