# Squares Counting GRIDSQRS Solution Codechef

Page Contents

## Squares Counting GRIDSQRS Solution

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).

## SOLUTION

Program Python: Squares Counting GRIDSQRS Solution in Python

```import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0){
int n = sc.nextInt();
int mat[][] = new int[n][n];
int cnt = 0;

for(int i = 0 ; i < n ; i++){
String str = sc.next();
for(int j = 0 ; j < n ; j++){
mat[i][j] = Integer.parseInt(str.charAt(j)+"");
if(mat[i][j] == 1)
cnt++;
}
}

if(n == 1){
System.out.println(cnt);
continue;
}
int row[][] = new int[n+2][n+2];
int col[][] = new int[n+2][n+2];

for(int i = 0 ; i <= n ; i++){
row[i] = 0;
row[i] = 0;
col[i] = 0;
col[i] = 0;
}

for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++){
if(mat[i-1][j-1] == 0){
row[i][j] = 0;
col[i][j] = 0;
}
else{
row[i][j] = row[i][j-1]+1;
col[i][j] = col[i-1][j]+1;
}
}
}

for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++){
for(int k = 2; k <= i && k <= j; k++){

int a = row[i-k+1][j] - row[i-k+1][j-k];
if(a != k)
continue;

int b = row[i][j] - row[i][j-k];
if(b != k)
continue;

int c = col[i][j] - col[i-k][j];
if(c != k)
continue;

int d = col[i][j-k+1] - col[i-k][j-k+1];
if(d != k)
continue;
cnt++;
}
}
}
System.out.println(cnt);

}
}
}
```

Program C++: Squares Counting GRIDSQRS Solution in C++

```#include<bits/stdc++.h>
using namespace std;

#define ll long long

int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int arr[n][n];
for(int i=0; i<n; i++)
{
string s;
cin>>s;
for(int j=0; j<n; j++)
{
arr[i][j] = int(s[j])-48;
}
}

ll ans = 0;
int hor[n][n], ver[n][n];
memset(hor, 0, sizeof(hor));
memset(ver, 0, sizeof(ver));

for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(arr[i][j] == 1)
{
hor[i][j] = (j==0) ? 1 : hor[i][j-1] + 1;
ver[i][j] = (i==0) ? 1 : ver[i-1][j] + 1;
}
}
}

for(int i=n-1; i>=0; i--)
{
for(int j=n-1; j>=0; j--)
{
int small = min(hor[i][j], ver[i][j]);
while(small > 0)
{
if(hor[i-small+1][j] >= small && ver[i][j-small+1] >= small)
ans++;
small--;
}
}
}

cout<<ans<<endl;
}

return 0;
}```