4228: 求出黑色格子形成的连通分量的数量

内存限制：1024 MB 时间限制：2.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

# Do use hexagon grid ## 题目描述 我们有一个如下所示的无限大的六边形网格。最初，所有格子都是白色的。 ![20241210151711_6757eaf747219.png](/upload/image/20241210/20241210151711_6757eaf747219.png) 一个六边形格子可以用两个整数 $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$ 个格子 $(X_1,Y_1),(X_2,Y_2),\cdots,(X_N,Y_N)$ 涂成黑色。 请求出黑色格子形成的连通分量的数量。 这里，如果两个黑色格子之间可以通过若干个相邻的黑色格子移动到达，则认为这两个黑色格子属于同一个连通分量。

输入

## 输入格式 输入按以下格式从标准输入给出: $N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$

输出

## 输出格式 输出所求答案。

样例输入 复制 

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

样例输出 复制 

3

提示

## 输入输出样例 ### 输入样例1 ``` 6 -1 -1 0 1 0 2 1 0 1 2 2 0 ``` ### 输出样例1 ``` 3 ``` ### 输入样例2 ``` 4 5 0 4 1 -3 -4 -2 -5 ``` ### 输出样例2 ``` 4 ``` ### 输入样例3 ``` 5 2 1 2 -1 1 0 3 1 1 -1 ``` ### 输出样例3 ``` 1 ``` ## 数据范围与提示 【样例1说明】 小高将格子涂黑后，网格如下图所示。 ![20241210151711_6757eaf747339.png](/upload/image/20241210/20241210151711_6757eaf747339.png) 黑色格子形成以下三个连通分量: (-1,-1) (1,0),(2,0) (0,1),(0,2),(1,2) 【数据范围】 输入中的所有值都是整数 $1 \le N \le 1000$ $|X_i|,|Y_i| \le 1000$ $(X_i,Y_i)$ 两两不同。 ## 题目来源 ABC269D
提交提交记录统计露一手!