# coreBugZJ

## Suneast’s blocks ， FZU 2011年3月月赛之 B， FZU 2011

Problem 2011 Suneast’s blocks

## Problem Description

Suneast loves playing with blocks so much. He has many small triangle blocks: He always likes using these small block to make a bigger one: The size of the small triangle is 1 and different block has different color, each color is expressed using an UPPER case alpha, so we can represent the big triangle above as the figure shows on the right.('~' means BLANK here)

Now, Suneast want to know, what is the size of the largest sub-strangle with the same color within the bigger one.

## Input

The first line of the input data is an integer number T, represent the number of test cases.

The first line of each test case has an integer N (1<=n<=100), means the height of the big triangle. Then following N lines, each line has exactly 2*i-1 UPPER case letters represent the small triangle.

## Output

For each test case, output a single line “Case %d: The largest block is %d.”, the first %d means the current case index, and the second %d is the size of the largest block.

3
3
A
BCD
EFDDD
4
A
CCA
CAAAC
CACACAC
4
T
ORZ
DAXIA
YAYAMAO

## Sample Output

Case 1: The largest block is 4.
Case 2: The largest block is 4.
Case 3: The largest block is 1.

## Source

FOJ有奖月赛-2011年03月

1 #include <stdio.h>
2 #include <string.h>
3
4 #define  L  209
5
6 int n, f[ L ][ L ], g[ L ][ L ];
7 char  tri[ L ][ L ];
8
9 int checkF( int i, int j ) {
10         int a = ( (tri[i+1][j-1]==tri[i][j]) ? f[i+1][j-1] : 0 );
11         int b = ( (tri[i+1][j+1]==tri[i][j]) ? f[i+1][j+1] : 0 );
12         int c = ( a < b ? a : b );
13         return f[ i ][ j ] = ( (tri[i+1][j]==tri[i][j]) ? (c+1) : 1 );
14 }
15
16 int checkG( int i, int j ) {
17         int a = ( (tri[i-1][j-1]==tri[i][j]) ? g[i-1][j-1] : 0 );
18         int b = ( (tri[i-1][j+1]==tri[i][j]) ? g[i-1][j+1] : 0 );
19         int c = ( a < b ? a : b );
20         return g[ i ][ j ] = ( (tri[i-1][j]==tri[i][j]) ? (c+1) : 1 );
21 }
22
23 int solve() {
24         int i, j, h = 0, tmp, ans = 0;
25         for ( i = n; i >= 1--i ) {
26                 for ( j = n-i+1; j <= n+i-1; j+=2 ) {
27                         tmp = checkF( i, j );
28                         if ( tmp > h ) {
29                                 h = tmp;
30                         }
31                 }
32         }
33         for ( i = 2; i <= n; ++i ) {
34                 for ( j = n-i+2; j <= n+i-1; j+=2 ) {
35                         tmp = checkG( i, j );
36                         if ( tmp > h ) {
37                                 h = tmp;
38                         }
39                 }
40         }
41         for ( i = 1; i <= h; ++i ) {
42                 ans += i + i - 1;
43         }
44         return ans;
45 }
46
47 char next() {
48         char ch;
49         do {
50                 ch = getchar();
51         } while ( (ch<'A'|| ('Z'<ch) );
52         return ch;
53 }
54
55 int main() {
56         int td, cd = 0, i, j;
57         scanf( "%d"&td );
58         while ( td-- > 0 ) {
59                 memset( tri, 0sizeof(tri) );
60                 memset( f, 0sizeof(f) );
61                 memset( g, 0sizeof(g) );
62                 scanf( "%d"&n );
63                 for ( i = 1; i <= n; ++i ) {
64                         for ( j = n-i+1; j <= n+i-1++j ) {
65                                 tri[ i ][ j ] = next();
66                         }
67                 }
68                 printf( "Case %d: The largest block is %d.\n"++cd, solve() );
69         }
70         return 0;
71 }
72

posted on 2011-03-20 19:01 coreBugZJ 阅读(1150) 评论(0)  编辑 收藏 引用 所属分类: ACM 