题目内容

你负责一个大型办公园区的无线网络部署。园区可以视作一个 $m*n$ 的网格，每个网格位置可以放置个无线接入点。每个无线接入点可以覆盖其所在位置。如果两个无线接入点的覆盖区域相连，则它们构成一个子网(一个接入点的上下左右、上左、上右、下左、下右如果有其他接入点则认为相连构成子网)，现在需要通过光纤将不同的子网俩俩相连。

你的任务是计算所有子网俩俩相连需要多少条光纤链路（如 $A、B、C$ 三个子网应该建立 $AB、AC、BC$ 三条链路）

输入描述

题面描述

给定一个大小为$m*n$ 的网格，每个格子上可能放置一个无线接入点（用值 1 表示）或不放置（用值 0 表示）。如果两个无线接入点的覆盖区域相连，则它们属于同一个子网。邻接关系包括上下左右以及四个对角方向（共 8 个方向）。现要求通过光纤将不同的子网两两相连，即如果共有$k$个子网，则需要建立${k(k-1)}{2}$ 条链路。请计算给定网格中所有子网两两相连需要多少条光纤链路。

问题本质分析

本质上是一个典型的「在二维网格中统计连通分量」问题，但邻接方式为 8 方向（包括对角线方向）。在网格中，每个放置了接入点的位置相当于一个「节点」，在 8 个方向上如果相邻也是放置的位置，则二者相连。目标是统计网格中有多少个这样的连通子网（连通分量），记为$k$，然后输出子网两两相连所需链路数：

$