P16838 [GKS 2021 #A] L Shaped Plots

给定一个 $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 形的个数。

在样例 #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 完成