Squares Counting GRIDSQRS Solution Codechef

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.

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

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

Leave a Comment

three − 2 =