高盛 OA 面试真题解析：Counting Connections in a Matrix 统计矩阵中的连通连接

Given a matrix of size m x n, m denotes the row starting with index 0 and n denotes the column starting with index 0.

The elements in the matrix are populated with values either 1 or 0. 1 indicates the matrix position is available for establishing the connection and 0 indicates the matrix position is not available for establishing the connection.

We need to connect the available adjacent positions vertically, horizontally, and diagonally and count the number of distinct connections established.

For example, given a matrix of size 3 x 4, the elements are stored as follows:

1 0 0 1
0 1 1 1
1 0 0 1

The expected output is 8.

In the above example, the positions are connected as follows and hence 8 connections are possible:

• (0,0) -> (1,1)
• (2,0) -> (1,1)
• (1,1) -> (1,2)
• (1,2) -> (0,3)
• (1,2) -> (1,3)
• (1,2) -> (2,3)
• (0,3) -> (1,3)
• (1,3) -> (2,3)

Input:

• m – integer – number of rows
• n – integer – number of columns
• m * n matrix

这道高盛 OA 题本质上是在统计二维网格中所有值为 1 的位置之间、相邻方向（上下左右与 4 个对角方向）可建立的连接数。解题时通常遍历矩阵中的每个 1，并检查它周围 8 个方向是否也为 1；为了避免把同一条连接重复计算，常见做法是只统计“成对连接”并在最后除以 2，或者只朝固定方向统计。样例 3 x 4 矩阵中共有 8 条连接，说明题目关注的是所有相邻 1 之间的无向边数量。