题面描述
给定一个大小为m∗n 的网格，每个格子上可能放置一个无线接入点（用值 1 表示）或不放置（用值 0 表示）。如果两个无线接入点的覆盖区域相连，则它们属于同一个子网。邻接关系包括上下左右以及四个对角方向（共 8 个方向）。现要求通过光纤将不同的子网两两相连，即如果共有k个子网，则需要建立k(k−1)2 条链路。请计算给定网格中所有子网两两相连需要多少条光纤链路。
问题本质分析
本质上是一个典型的「在二维网格中统计连通分量」问题，但邻接方式为 8 方向（包括对角线方向）。在网格中，每个放置了接入点的位置相当于一个「节点」，在 8 个方向上如果相邻也是放置的位置，则二者相连。目标是统计网格中有多少个这样的连通子网（连通分量），记为k，然后输出子网两两相连所需链路数：
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
