题目描述

给定一个 $R$ 行 $C$ 列的网格，每个格子中的值为 $0$ 或 $1$。

一个段是指同一行或同一列中连续的非空单元格序列。段的长度定义为该序列中单元格的个数。

如果一个段中的所有单元格均为 $1$，则称该段为“好”段。

一个 L 形 定义为一对无序的段，满足以下所有性质：

• 每个段都必须是“好”段。
• 两个段必须互相垂直。
• 两个段必须共享一个单元格，且该单元格是两个段的端点。
• 每个段的长度至少为 $2$。
• 较长段的长度是较短段长度的两倍。

我们需要计算网格中 L 形的个数。

以下展示了两个正确的 L 形示例：

:::align{center} :::

以及三个无效 L 形的示例：

:::align{center} :::

注意，左侧的形状中，两个段没有共享共同的端点。接下来的两个形状不满足最后一个要求：中间的形状两个段长度相等，最后一个形状中较长段的长度大于较短段长度的两倍。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含两个整数 $R$ 和 $C$。

随后 $R$ 行，每行包含 $C$ 个整数，表示网格中的单元格。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 L 形的个数。

2
4 3
1 0 0
1 0 1
1 0 0
1 1 0
6 4
1 0 0 0
1 0 0 1
1 1 1 1
1 0 1 0
1 0 1 0
1 1 1 0

Case #1: 1
Case #2: 9

提示

在样例 #1 中，存在 $1$ 个 L 形。

• 第 $1$ 个由单元格 $(1,1), (2,1), (3,1), (4,1), (4,2)$ 构成。

:::align{center} :::

在样例 #2 中，存在 $9$ 个 L 形。

• 第 $1$ 个由单元格 $(1,1), (2,1), (3,1), (4,1), (5,1), (6,1), (6,2), (6,3)$ 构成。
• 第 $2$ 个由单元格 $(3,1), (4,1), (5,1), (6,1), (6,2)$ 构成。
• 第 $3$ 个由单元格 $(6,1), (5,1), (4,1), (3,1), (3,2)$ 构成。
• 第 $4$ 个由单元格 $(3,3), (4,3), (5,3), (6,3), (6,2)$ 构成。
• 第 $5$ 个由单元格 $(6,3), (5,3), (4,3), (3,3), (3,2)$ 构成。
• 第 $6$ 个由单元格 $(3,1), (3,2), (3,3), (3,4), (2,4)$ 构成。
• 第 $7$ 个由单元格 $(3,4), (3,3), (3,2), (3,1), (2,1)$ 构成。
• 第 $8$ 个由单元格 $(3,4), (3,3), (3,2), (3,1), (4,1)$ 构成。
• 第 $9$ 个由单元格 $(6,3), (5,3), (4,3), (3,3), (3,4)$ 构成。

下图中展示了前 $3$ 个 L 形。

:::align{center} :::

限制条件

$1 \le T \le 100$。

网格仅由 $0$ 和 $1$ 组成。

测试集 1

$1 \le R \le 40$。

$1 \le C \le 40$。

测试集 2

最多 $5$ 个测试用例满足 $1 \le R \le 1000$ 且 $1 \le C \le 1000$。

其余测试用例满足 $1 \le R \le 40$ 且 $1 \le C \le 40$。

翻译由 DeepSeek V4 Pro 完成