Breaking

Saturday, 1 July 2017

Max Same Letter Square Size

             Max Same Letter Square Size 

Certain kids were playing a game in which they would draw a N*N matrix and would fill in a letter from A to Z in a given cell based on certain rules.
Without getting into the details of those rules, the final values present in the N*N matrix is passed as the input to the program.
The program must print the size of the largest square sub-matrix which has all the letters equal in it.

Input Format:
The first line will contain N.
The next N lines will each contain N letters separated by a space.

Output Format:
The first line will contain the size of the largest square sub-matrix with all the letters equal in it.

Boundary Conditions:
3 <= N <= 50

Example Input/Output 1:
 Input:
5
A H K L O
 J H H B U
Q H H H Z
 I E H H W
F H H W Z

 Output:
2
Explanation: 
The two 2*2 sub-matrices filled with H are the largest.

Example Input/Output 1: 
Input:
7
B C C C C J K
O P Q R S T C
 H S S S S S S
 J K S S S S S
 K I S S S S U
 G H S S S S V
 Y Y Y X D Q T


Output:
  4

Explanation:

The 4*4 sub-matrix filled with S is the largest.


Code:


#include <iostream>
using namespace std;
int main(){
 int num,i,j,c,x,y,k,l,max=0;
 cin>>num;
 char a[num][num];
 for(i=0;i<num;i++)
 for(j=0;j<num;j++)
 cin>>a[i][j];
 for(i=0;i<num;i++)
 {
 for(j=0;j<num;j++)
 {
     if(a[i][j]==a[i][j+1] && a[i][j]==a[i+1][j])
     {
         x=0;
         y=0;
         for(k=i;k<num;k++){
         if(a[k][j]!=a[i][j])
             break;
             x++;
         }
         for(k=j;k<num;k++){
         if(a[i][k]!=a[i][j])
         break;
         y++;
         }
         c= min(x,y);
     }   
     for(k=i;k<i+c;k++){
     for(l=j;l<j+c;l++)
     if(a[k][l]!=a[i][j])
     break;
         if(j+c>l)
         break;
         }
         if(k==i+c && l==j+c && max<c)
         max=c;
 }
 }
 cout<<max;
 return 0;
}

No comments:

Post a Comment

Like