Squares Counting Solution | DEC LONG CHALLENGE | Codechef

You are given a binary square matrix AA of size N×NN×N. Let the value at cell (i,j)(i,j) be denoted by A(i,j)A(i,j).

Your task is to count the number of square frames present in the grid. A square frame is defined to be a square submatrix of AA whose border elements are all ‘1’.

Formally,

• A square submatrix of AA of size kk with top-left corner (i,j)(i,j) is defined to be the set of cells {(i+x,j+y)∣0≤x,y<k}{(i+x,j+y)∣0≤x,y<k}. Note that this requires i+k−1≤Ni+k−1≤N and j+k−1≤Nj+k−1≤N.
• square frame of size kk with top-left corner (i,j)(i,j) is defined to be a square submatrix of size kk such that A(i+x,j+y)=A(i+x,j+y)= 1 whenever x=0x=0 or y=0y=0 or x=k−1x=k−1 or y=k−1y=k−1. There is no constraint on the values of elements strictly inside the frame.

Refer to the sample explanation for more details.

Input Format

The first line of input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.

The first line of each test case contains a single integer NN denoting the size of the grid.

Each of the next NN lines contains a string consisting of NN characters. The ii-th such string represents the ii-th row of AA. Each character of each string is either 0 or 1.

Output Format

For each test case, output a single integer denoting the count of square frames in the grid.

Constraints

• 1≤T≤1051≤T≤105
• 1≤N≤5001≤N≤500
• The grid is binary, i.e, A(i,j)=A(i,j)= 0 or 1 for every 1≤i,j≤N1≤i,j≤N.
• Sum of N2N2 over all test cases does not exceed 106106.

2
2
10
00
4
1111
1101
1011
1111

1
17

Explanation

Test Case 11: There is 11 square frame, the submatrix containing index (1,1)(1,1).

Test Case 22: There are 1414 square frames of size 11, 22 of size 22, and 11 of size 44.

Some of the square frames are :

• The frame of size 11 containing point (3,3)(3,3).
• The frame of size 22 with corner points (1,1),(1,2),(2,2),(2,1)(1,1),(1,2),(2,2),(2,1).
• The frame of size 22 with corner points (3,3),(4,3),(4,4),(3,4)(3,3),(4,3),(4,4),(3,4).
• The frame of size 44 with corner points (1,1),(1,4),(4,4),(4,1)(1,1),(1,4),(4,4),(4,1).

SOLUTION

Will be updated today.