Squares Counting Solution | DEC LONG CHALLENGE | Codechef

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.

Subtasks

Subtask 1(100 points): Original constraints

Sample Input 1 

2
2
10
00
4
1111
1101
1011
1111

Sample Output 1 

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.

Refer and Earn Rs. 1200 per referral on Upstox

Click here to know more

Read More Post Here

Leave a Comment

Your email address will not be published. Required fields are marked *

x