CF2245H Connect Connect See

给定一个由 $n$ 行 $m$ 列组成的矩形网格 $a$，每个单元格 $(i,j)$ 上写有一个非负整数，记为 $a_{i,j}$。 在网格 $a$ 上，长度为 $k$ 的路径 $p$ 定义为一系列单元格 $p_0, p_1, \ldots, p_k$，满足对于每个 $0 \leq i < k$，$p_i$ 与 $p_{i+1}$ 在网格上相邻边，并且所有 $p_i$ 互不相同。长度为 $k$ 的简单路径 $p$ 的转弯数，记为 $t(p)$，定义为所有满足下列条件的下标 $1 \leq i < k$ 的数量： - 设 $p_j=(x_j, y_j)$，对于 $j \in \{i-1, i, i+1\}$。若 $x_{i-1}\neq x_{i+1}$ 且 $y_{i-1}\neq y_{i+1}$ 均成立，则为一次转弯。 路径 $p=[(x_0,y_0),(x_1,y_1),\ldots,(x_k,y_k)]$ 当且仅当同时满足以下条件时被视为有效： - $k \geq 1$。 - $t(p) \leq 2$。 - $a_{x_0,y_0}=a_{x_k,y_k}$，$a_{x_0,y_0} > 0$，且对所有 $1 \leq i < k$，$a_{x_i,y_i}=0$。 若存在一条有效路径 $p$，其起点为 $(u_1,v_1)$，终点为 $(u_2,v_2)$，则称无序点对 $(u_1,v_1)$ 和 $(u_2,v_2)$ 是可连通的。 请你统计网格 $a$ 中可连通的点对数量。

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例数。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 100$，$1 \leq n \cdot m \leq 2 \times 10^6$），表示网格 $a$ 的大小。 接下来 $n$ 行，每行包含 $m$ 个整数 $a_{i,1}, a_{i,2},\ldots,a_{i,m}$（$0 \leq a_{i,j} \leq n \cdot m$），表示第 $i$ 行的网格值。 保证所有测试用例中 $n \cdot m$ 之和不超过 $2 \times 10^6$。

对于每个测试用例，输出一个整数，表示网格 $a$ 中可连通的点对数量。

在第 1 和第 2 个测试用例中，网格里没有可连通的点对。 在第 3 个测试用例中，可连通的点对为： - $(1,1),(1,2)$ - $(1,2),(2,2)$ - $(1,1),(2,2)$ 在第 6 个测试用例中，共有 $34$ 个可连通的点对。其中之一为 $(1,1),(3,3)$。注意 $(1,1),(5,5)$ 不是可连通点对，因为任何从 $(1,1)$ 到 $(5,5)$ 的路径转弯次数都大于 $2$。 由 ChatGPT 5 翻译