[UVA] 10908 - Largest Square
4th IIUC Inter-University Programming Contest, 2005 |
|
| D |
Largest Square |
| Input: standard input |
|
| Problemsetter: Tanveer Ahsan |
|
Given a rectangular grid of characters you have to find out the length of a side of the largest square such that all the characters of the square are same and the center [intersecting point of the two diagonals] of the square is at location (r, c). The height and width of the grid is M and N respectively. Upper left corner and lower right corner of the grid will be denoted by (0, 0) and (M-1, N-1) respectively. Consider the grid of characters given below. Given the location (1, 2) the length of a side of the largest square is 3.
abbbaaaaaa
abbbaaaaaa
abbbaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaccaaaaaa
aaccaaaaaa
Input
The input starts with a line containing a single integer T (< 21). This is followed by T test cases. The first line of each of them will contain three integers M, N and Q (< 21) separated by a space where M, N denotes the dimension of the grid. Next follows M lines each containing N characters. Finally, there will be Q lines each containing two integers r and c. The value of M and N will be at most 100.
Output
For each test case in the input produce Q+1 lines of output. In the first line print the value of M, N and Q in that order separated by single space. In the next Q lines, output the length of a side of the largest square in the corresponding grid for each (r, c) pair in the input.
| Sample Input |
Output for Sample Input |
| 1 |
7 10 4 |
#include <stdio.h>
#include <stdlib.h>
int main() {
int T;
char map[102][102];
int i, M, N, Q, x, y;
scanf("%d", &T);
while(T--) {
scanf("%d %d %d", &M, &N, &Q);
getchar();
for(i = 0; i < M; i++)
gets(map[i]);
printf("%d %d %d\n", M, N, Q);
while(Q--) {
scanf("%d %d", &x, &y);
int ans = 1;
int i, a, b;
for(i = 0; i <= M || i <= N; i++) {
int flag = 0;
for(a = x-i; a <= x+i; a++) {
for(b = y-i; b <= y+i; b++) {
if(a < 0 || b < 0 || a >= M || b >= N) {
flag = 1;break;
}
if(map[a][b] != map[x][y])
flag = 1;
}
}
if(flag == 0) {
if(ans < 2*i+1)
ans = i*2+1;
} else
break;
}
printf("%d\n", ans);
}
}
return 0;
}