← 返回题目列表

Codeforces · 11/C

C. 有多少个正方形?

中文机器翻译题面 查看原题

给定一个 0-1 矩形矩阵。其中有多少个正方形?正方形是线宽等于 1 的实心正方形框架(边框)。正方形应至少为 2 × 2。我们只对两种类型的正方形感兴趣:

1. 每条边与矩阵的一条边平行的正方形;
2. 每条边平行于矩阵对角线的正方形。

无论哪种类型,一个正方形必须至少包含一个 1,并且不能接触(边或角)任何外来 1。当然,每个正方形的边长应该相等。

给定矩阵中有多少个方格?

输入

第一行包含整数 t (1 ≤ t ≤ 10000),其中 t 是输入中测试用例的数量。然后是测试用例。每个案例都以包含整数 n 和 m (2 ≤ n, m ≤ 250) 的行开始,其中 n 是行数,m 是列数。以下 n 行每行包含 m 个字符(0 或 1)。

对于任何输入文件,所有测试用例中的字符总数不超过 106。

输出

您应该准确输出 t 行,并在第 i 行输出第 i 个测试用例的答案。

示例

输入 #1

2
8 8
00010001
00101000
01000100
10000010
01000100
00101000
11010011
11000011
10 10
1111111000
1000001000
1011001000
1011001010
1000001101
1001001010
1010101000
1001001000
1000001000
1111111000

输出 #1

1
2

输入 #2

1
12 11
11111111111
10000000001
10111111101
10100000101
10101100101
10101100101
10100000101
10100000101
10111111101
10000000001
11111111111
00000000000

输出 #2

3