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