Codeforces Beta Round 11 |
---|
Закончено |
Вам задана прямоугольная матрица, состоящая из нулей и единиц. Ваша задача посчитать число квадратов в ней. В данном случае квадратом называется рамка (бордюр) ширины 1 квадратной формы. Минимальный размер квадрата 2 × 2. Существует два типа квадратов:
Этот пример содержит единственный квадрат первого типа:
0000000
0111100
0100100
0100100
0111100
А этот — квадрат второго типа:
0000000
0010000
0101000
0010000
0000000
Независимо от типа квадраты не могут касаться лишних единиц (как по стороне так и по углу). Конечно, длины сторон для любого квадрата равны между собой.
Напишите программу, которая выводит количество квадратов на заданной матрице.
Первая строка содержит целое число t (1 ≤ t ≤ 10000), где t это количество наборов входных данных в тесте. Далее следуют сами наборы. Каждый набор начинается строкой, состоящей из двух целых чисел n and m (2 ≤ n, m ≤ 250), где n это количество строк, а m — количество столбцов заданной матрицы. Следующие n строк содержат по m символов каждая: (символы 0 или 1).
Суммарное количество элементов во всех матрицах для одного теста не превосходит 106.
Выведите t строк, i-ая строка должны содержать ответ для i-го набора входных данных.
2
8 8
00010001
00101000
01000100
10000010
01000100
00101000
11010011
11000011
10 10
1111111000
1000001000
1011001000
1011001010
1000001101
1001001010
1010101000
1001001000
1000001000
1111111000
1
2
1
12 11
11111111111
10000000001
10111111101
10100000101
10101100101
10101100101
10100000101
10100000101
10111111101
10000000001
11111111111
00000000000
3
Название |
---|