题面描述

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

问题本质分析

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

$\text{答案} = \binom{k}{2} = \frac{k(k-1)}{2}.$

• 网格规模最大可达$m*n$，其中$m,n<2000$，故格子总数可达近$4\times10^6$。需要在时间上做到$O(mn)$ 复杂度，空间上也需$O(mn)$ 较低常数额外空间。

• 统计连通分量常用的方法有 DFS/BFS 或并查集（DSU）。

  • DFS 递归可能会因为深度过大而栈溢出，不推荐使用递归方式。可用显式栈的迭代 DFS，但 BFS 同样可行。
  • BFS 需额外队列，最坏情况下队列可能很大，但此场景常见可以接受。
  • 并查集需要对每个“1”节点进行编号，并在遍历时与已访问到的相邻“1”进行合并；并查集结构大小为总格子数（或仅“1”的个数），常数略高，但也可行。不过简单 BFS 更直观。

• 由于只需最终的连通分量个数$k$，可以在遍历时对每个未访问的“1”启动一次 BFS，将该连通分量中的所有“1”标记为已访问，计数加一。遍历完成后得到$k$，再计算${k(k-1)}{2}$，使用 64 位整数保存结果。

思路

1. 读入：读取整数$m,n$，再读入$m$ 行、每行$n$个0/1，存入二维数组（或扁平一维数组）。

2. 初始化：准备同样尺寸的布尔访问数组 visited，用于标记哪些格子已被纳入某个连通分量。

3. 遍历网格：双重循环遍历每个位置$(i,j)$：

   • 如果该位置值为 1 且未被访问：

     • 启动一次 BFS/DFS，将此连通分量中所有可达位置遍历并标记访问。
     • 连通方向为 8 个方向：dx = {-1,-1,-1,0,0,1,1,1}, dy = {-1,0,1,-1,1,-1,0,1}
     • BFS 典型做法：用队列存储待访问节点，对每个出队节点，对 8 个方向进行越界检查、是否为 1、是否未访问，若满足则标记并入队。
     • BFS 结束后，连通分量计数器 count 增加 1。

4. 遍历结束后得到子网数量$k={count}$。

5. 计算答案：使用 64 位整数，${ans} = \frac{k \times (k-1)}{2}$。注意可能 $k$ 很大（最坏每个“1”都孤立时），但$k\le mn \approx 4\times10^6$，$k(k-1)/2 \approx 8\times10^{12}$，符合 64 位范围。

6. 输出 答案。

• 时间复杂度：$O(mn)$，每个格子最多进队和出队一次，访问常数方向。
• 空间复杂度：存储网格需$O(mn)$，访问数组$O(mn)$，BFS 队列最坏$O(mn)$。总体在题目给定内存限制内（C++ 256MB，其他语言 512MB 足够）。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    cin >> m >> n;
    // 存储网格，0/1
    vector<vector<char>> grid(m, vector<char>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;
            grid[i][j] = (char)x;
        }
    }
    // 访问标记
    vector<vector<char>> visited(m, vector<char>(n, 0));
    // 8 个方向偏移
    const int dx[8] = {-1,-1,-1, 0, 0, 1, 1, 1};
    const int dy[8] = {-1, 0, 1,-1, 1,-1, 0, 1};

    long long count = 0; // 子网计数
    queue<pair<int,int>> q;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 如果是接入点且未访问，则启动 BFS
            if (grid[i][j] == 1 && !visited[i][j]) {
                count++;
                visited[i][j] = 1;
                q.emplace(i, j);
                while (!q.empty()) {
                    auto [x, y] = q.front();
                    q.pop();
                    // 遍历 8 个方向
                    for (int dir = 0; dir < 8; dir++) {
                        int nx = x + dx[dir];
                        int ny = y + dy[dir];
                        // 边界检查
                        if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                            // 如果该位置是接入点且未访问
                            if (grid[nx][ny] == 1 && !visited[nx][ny]) {
                                visited[nx][ny] = 1;
                                q.emplace(nx, ny);
                            }
                        }
                    }
                }
            }
        }
    }
    // 计算需要的光纤链路数量：k 个子网需要 k*(k-1)/2 条
    long long k = count;
    long long ans = k * (k - 1) / 2;
    cout << ans;
    return 0;
}

Python

import sys
from collections import deque

def main():
    data = sys.stdin.readline().split()
    if not data:
        return
    m, n = map(int, data)
    grid = [None] * m
    for i in range(m):
        # 读取一行 n 个整数
        row = sys.stdin.readline().split()
        # 转为整数 0/1
        grid[i] = [int(x) for x in row]

    visited = [[False] * n for _ in range(m)]
    dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
    count = 0
    dq = deque()

    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1 and not visited[i][j]:
                count += 1
                visited[i][j] = True
                dq.append((i, j))
                # BFS 遍历连通分量
                while dq:
                    x, y = dq.popleft()
                    for dx, dy in dirs:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < m and 0 <= ny < n:
                            if grid[nx][ny] == 1 and not visited[nx][ny]:
                                visited[nx][ny] = True
                                dq.append((nx, ny))
    k = count
    # 使用 Python 整数自动大整数支持
    ans = k * (k - 1) // 2
    print(ans)

if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        // 读取网格
        int[][] grid = new int[m][n];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        boolean[][] visited = new boolean[m][n];
        // 8 个方向
        int[] dx = {-1,-1,-1, 0, 0, 1, 1, 1};
        int[] dy = {-1, 0, 1,-1, 1,-1, 0, 1};

        long count = 0;
        Deque<int[]> queue = new ArrayDeque<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    // 新连通分量
                    count++;
                    visited[i][j] = true;
                    queue.add(new int[]{i, j});
                    while (!queue.isEmpty()) {
                        int[] cur = queue.poll();
                        int x = cur[0], y = cur[1];
                        // 遍历 8 方向
                        for (int dir = 0; dir < 8; dir++) {
                            int nx = x + dx[dir];
                            int ny = y + dy[dir];
                            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                                if (grid[nx][ny] == 1 && !visited[nx][ny]) {
                                    visited[nx][ny] = true;
                                    queue.add(new int[]{nx, ny});
                                }
                            }
                        }
                    }
                }
            }
        }
        long k = count;
        long ans = k * (k - 1) / 2;
        System.out.println(ans);
    }
}

题目内容

你负责一个大型办公园区的无线网络部署。园区可以视作一个 $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$