Squares Counting GRIDSQRS Solution Codechef

by

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 or 1.

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 or 1 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

Leave a Comment

eighteen + 17 =