A7358 | 小午历险记之蜂巢信标
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
在一片无限延伸的蜂巢状区域中，所有的六边形单元最初都是未激活状态。每一个六边形单元可以用一对整数坐标 $(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), \dots, (X_N, Y_N)$
如果两个激活的单元之间，可以通过若干步每一步都移动到相邻的激活单元互相到达，那么它们属于同一个信标网络。
请找出这些激活的单元一共形成了多少个互不连通的信标网络。
在这种蜂巢网格中，单元 $(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), \dots, (X_N, Y_N)$
如果两个激活的单元之间，可以通过若干步每一步都移动到相邻的激活单元互相到达，那么它们属于同一个信标网络。
请找出这些激活的单元一共形成了多少个互不连通的信标网络。
输入格式
第一行一个整数 $N$。
接下来 $N$ 行，每行两个整数 $X_i, Y_i$，表示一个被激活的蜂巢单元坐标。
接下来 $N$ 行，每行两个整数 $X_i, Y_i$，表示一个被激活的蜂巢单元坐标。
输出格式
输出一个整数，表示信标网络的数量。
输入输出样例
输入 #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 \le N \le 1000$ ， 所有坐标 $(X_i, Y_i)$ 两两不同， 坐标范围在有限区域内，但蜂巢网格本身视为无限大
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？