题面描述
给定一个大小为m∗n 的网格，每个格子上可能放置一个无线接入点（用值 1 表示）或不放置（用值 0 表示）。如果两个无线接入点的覆盖区域相连，则它们属于同一个子网。邻接关系包括上下左右以及四个对角方向（共 8 个方向）。现要求通过光纤将不同的子网两两相连，即如果共有k个子网，则需要建立k(k−1)2 条链路。请计算给定网格中所有子网两两相连需要多少条光纤链路。
问题本质分析
本质上是一个典型的「在二维网格中统计连通分量」问题，但邻接方式为 8 方向（包括对角线方向）。在网格中，每个放置了接入点的位置相当于一个「节点」，在 8 个方向上如果相邻也是放置的位置，则二者相连。目标是统计网格中有多少个这样的连通子网（连通分量），记为k，然后输出子网两两相连所需链路数：
题目内容
在一个大型办公园区中，需要部署无线网络。园区平面被划分为 m×n 个网格单元，每个单元可以放置一个无线接入点。每个单元的状态用一个整数表示：1 表示该单元放置了无线接入点，0 表示该单元没有放置接入点。
每个无线接入点的覆盖范围就是它所在的网格单元。如果两个无线接入点的覆盖区域相连，则它们属于同一个子网。这里的“相连”定义为：一个接入点与其上方、下方、左方、右方、左上方、右上方、左下方、右下方这八个相邻单元中的另一个接入点都视为覆盖区域相连。通过这种相邻关系相互连通的所有接入点共同构成一个子网。
现在需要用光纤将不同子网两两相连。要求任意两个不同的子网都必须直接通过一条光纤链路连接，同一个子网内部不需要光纤连接。给定整个网格中的接入点分布，请计算所需光纤链路的总数。若共有 k 个子网，则答案等于 2k(k−1)。
约束条件：
- 网格行数 m 与列数 n 满足 1≤m,n<2000。
- 每个单元的状态只能为
0 或 1。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
