首页 > 代码库 > 数正方形
数正方形
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
小B正在做一个关于图像理解方面的研究，她的目标是识别图像中的轮廓。当前阶段，她希望能够识别正方形。图像用一个矩阵表示，矩阵的每个元素对应于图像中的一个像素点，值为0或1，0表示背景，1表示前景。需要寻找的正方形必须满足线宽为单像素，且大小至少为2x2。她希望你能帮她找出图像中满足如下条件的两类正方形：
- 正方形的边与矩阵边缘平行；
- 正方形的边与矩阵对角线平行；
如以下矩阵中只有一个第一类正方形：
0000000
0111100
0100100
0100100
0111100
以下的矩阵中只有一个第二类正方形：
0000000
0010000
0101000
0010000
0000000
此外，不管何种类型的正方形，其每条边必须等长，且不能有任何边或顶点的像素与不属于该正方形的像素相连接。
输入中有多组测试数据。第一行为一个整数t（1 =< t =< 10000），表示测试数据的组数，接下来是t组测试数据。每组测试数据的第一行为两个整数n和m（2<=n, m<=250），n和m分别为矩阵的行数和列数，接下来是n行数据，每行由m个0或1构成。
每个测试输入中的字符数不超过10^6个。
对每组测试数据，在单独的行中输出矩阵中符合要求的正方形的数量。
3
8 8
00010001
00101000
01000100
10000010
01000100
00101000
11010011
11000011
10 10
1111111000
1000001000
1011001000
1011001010
1000001101
1001001010
1010101000
1001001000
1000001000
1111111000
12 11
11111111111
10000000001
10111111101
10100000101
10101100101
10101100101
10100000101
10100000101
10111111101
10000000001
11111111111
00000000000
1
2
3
数正方形