题面描述

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

问题本质分析

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

$

题目内容

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

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

输入描述

第一行：两个整数 $m$ 和 $n$ ，分别表示网格的行数和列数 $(1≤m,n<2000)$

接下来的 $m$ 行，每行有 $n$ 个整数 $0$ 或 $1$ ，表示网格中每个位置的状态

$1$：表示该位置放置了无线接入点

$0$：表示该位置未放置无线接入点

输出描述

输出一个整数，表示所有子网俩俩相连需要的光纤链路数量

样例1

输入

4 5
1 1 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 1 0

输出

1

说明

网格中有两个子网：

第一个区域由位置 $(0,0)$ 和 $(1,0)$ 等组成，属于同一个子网。

第二个区域由位置 $(2,2)、(2,3)、(3,3)$ 等组成，属于另一个子网

故使用一个链路可以达成俩俩相连的目标

样例2

输入

2 2
1 0
0 1

输出

0

说明

网格中有一个子网：

由位置 $(0,0)$ 和 $(1,1)$ 等组成，属于同一个子网。

一个子网不需要使用光纤连接故结果为 $0$