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