Squares Counting GRIDSQRS Solution
You are given a binary square matrix A of size N×N. Let the value at cell (i,j) be denoted by 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 A whose border elements are all ‘1’.
Formally,
- A square submatrix of A of size k with top-left corner (i,j) is defined to be the set of cells {(i+x,j+y)∣0≤x,y<k}. Note that this requires i+k−1≤N and j+k−1≤N.
- A square frame of size k with top-left corner (i,j) is defined to be a square submatrix of size k such that A(i+x,j+y)=
1
whenever x=0 or y=0 or x=k−1 or y=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 T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N denoting the size of the grid.
- Each of the next N lines contains a string consisting of N characters. The i-th such string represents the ii-th row of A. Each character of each string is either
0
or1
.
Output Format
For each test case, output a single integer denoting the count of square frames in the grid.
Constraints
- 1≤T≤105
- 1≤N≤500
- The grid is binary, i.e, A(i,j)=
0
or1
for every 1≤i,j≤N. - Sum of N2 over all test cases does not exceed 106.
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 1: There is 1 square frame, the submatrix containing index (1,1).
Test Case 2: There are 14 square frames of size 1, 2 of size 2, and 1 of size 4.
Some of the square frames are :
- The frame of size 1 containing point (3,3)
- The frame of size 2 with corner points (1,1),(1,2),(2,2),(2,1).
- The frame of size 2 with corner points (3,3),(4,3),(4,4),(3,4).
- The frame of size 4 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] = 0;
row[0][i] = 0;
col[0][i] = 0;
col[i][0] = 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;
}
December Long Challenge 2021 Solution
- List of Lists LISTLIST Solution Codechef
- Valleys and Hills VANDH Solution Codechef
- Rock Paper Scissors ROPASCI Solution Codechef
- Squares Counting GRIDSQRS Solution Codechef
- Pyramid Traversal PYRAMIDMOVES Solution Codechef
- Increasing String INCREAST Solution Codechef
- Utkarsh and Placement tests UTKPLC Solution Codechef
- Check Mate CHECKMATE Solution Codechef