CF2245H.Connect Connect See

You are given a rectangular grid $a$ consisting of $n$ rows and $m$ columns. The $j$-th cell in the $i$-th row is denoted by $(i,j)$. There is a non-negative integer written in every cell. The integer written in cell $(i,j)$ is denoted by $a_{i,j}$.

A path $p$ of length $k$ on $a$ is defined as a sequence of cells $p_0,p_1,\ldots,p_k$ such that $p_i$ and $p_{i+1}$ share an edge for every $0 \le i \lt k$, and all $p_i$ are distinct. The number of turns of a simple path $p$ of length $k$, denoted by $t(p)$, is defined as the number of indices $1 \le i \lt k$ that satisfy the following condition:

• Let $p_j=(x_j,y_j)$ for $j \in {i-1,i,i+1}$. Then, both $x_{i-1} \ne x_{i+1}$ and $y_{i-1} \ne y_{i+1}$ hold.

A path $p=[(x_0,y_0),(x_1,y_1),\ldots,(x_k,y_k)]$ is considered valid if and only if all of the following conditions hold:

• $k \ge 1$.
• $t(p) \le 2$.
• $a_{x_0,y_0}=a_{x_k,y_k}$, $a_{x_0,y_0} \gt 0$, and $a_{x_i,y_i}=0$ for every $1 \le i \lt k$.

An unordered pair of cells $(u_1,v_1)$ and $(u_2,v_2)$ is considered connectable if and only if there exists a valid path $p$ of length $k$ such that $p_0=(u_1,v_1)$ and $p_k=(u_2,v_2)$.

Find the number of connectable pairs in $a$.

给你一个由 $n$ 行和 $m$ 列组成的矩形网格 $a$。第 $i$ 行第 $j$ 列的格子记为 $(i,j)$。每个格子中写有一个非负整数。格子 $(i,j)$ 中的整数记为 $a_{i,j}$。

网格 $a$ 上一条长度为 $k$ 的路径 $p$ 定义为一个格子序列 $p_0,p_1,\ldots,p_k$，满足：对每个 $0 \le i < k$，$p_i$ 与 $p_{i+1}$ 共享一条边（即相邻），且所有 $p_i$ 互不相同。一条长度为 $k$ 的简单路径 $p$ 的转向次数（记为 $t(p)$）定义为满足以下条件的下标 $i$（其中 $1 \le i < k$）的个数：

• 设 $p_j=(x_j,y_j)$，其中 $j \in \{i-1,i,i+1\}$，则同时满足 $x_{i-1} \ne x_{i+1}$ 且 $y_{i-1} \ne y_{i+1}$。

路径 $p=[(x_0,y_0),(x_1,y_1),\ldots,(x_k,y_k)]$ 被称为合法路径，当且仅当满足以下全部条件：

• $k \ge 1$。
• $t(p) \le 2$。
• $a_{x_0,y_0}=a_{x_k,y_k}$，$a_{x_0,y_0} > 0$，且对每个 $1 \le i < k$，均有 $a_{x_i,y_i}=0$。

无序格子对 $((u_1,v_1),(u_2,v_2))$ 被称为可连接的，当且仅当存在一条合法路径 $p$（长度为 $k$），使得 $p_0=(u_1,v_1)$ 且 $p_k=(u_2,v_2)$。

求网格 $a$ 中可连接的格子对的总数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 100$, $1 \le n \cdot m \le 2 \cdot 10^6$), representing the dimensions of $a$.

The $i$-th of the next $n$ lines contains $m$ integers $a_{i,1}, a_{i,2},\ldots,a_{i,m}$ ($0 \le a_{i,j} \le n \cdot m$), representing the $i$-th row of $a$.

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $2 \cdot 10^6$.

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 100$，$1 \le n \cdot m \le 2 \cdot 10^6$），表示矩阵 $a$ 的维度。

接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个整数 $a_{i,1}, a_{i,2},\ldots,a_{i,m}$（$0 \le a_{i,j} \le n \cdot m$），表示矩阵 $a$ 的第 $i$ 行。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $2 \cdot 10^6$。

For each test case, output an integer representing the number of connectable pairs in $a$.

对于每个测试用例，输出一个整数，表示数组 $a$ 中可连接的对数。

In the first and second test cases, there are no connectable pairs in $a$.

In the third test case, the connectable pairs are:

• $(1,1),(1,2)$.
• $(1,2),(2,2)$.
• $(1,1),(2,2)$.

In the sixth test case, there are $34$ connectable pairs. One of them is $(1,1),(3,3)$. Note that $(1,1),(5,5)$ is not a connectable pair, as any path that begins at $(1,1)$ and ends at $(5,5)$ has more than $2$ turns.

在第一和第二个测试用例中，数组 $a$ 中不存在可连接的点对。

在第三个测试用例中，可连接的点对有：

• $(1,1),(1,2)$。
• $(1,2),(2,2)$。
• $(1,1),(2,2)$。

在第六个测试用例中，共有 $34$ 个可连接的点对。其中之一是 $(1,1),(3,3)$。注意，$(1,1),(5,5)$ 不是一个可连接的点对，因为任何从 $(1,1)$ 出发、终止于 $(5,5)$ 的路径的转弯次数均超过 $2$ 次。