[Login|Register]
Problems

Status

Rank

Problem 1298
Matrix once more
Time Limit: 1000ms
Memory Limit: 65536kb
Description
Given an N*M matrix composed of uppercase letters 'A','B','C'. We define two sub-matrix named S and D.
The definition of sub-matrix S: a matrix with outermost layer composed by letter 'C' and internal layers (if existed) composed by letter 'A'.
The definition of sub-matrix D: a matrix with outermost layer composed by letter 'B' and internal layers (if existed) composed by letter 'C'.
Can you compute the maximum area of sub-matrix S and sub-matrix D in a given matrix respectively?
For example, a 3*5 matrix is below:
CCCCCB
CAAACB
CCCCCB
So the maximum area of sub-matrix S and sub-matrix D is 15 and 3 respectively.
Input
The first line, an integer T, indicates number of the test cases (T<=10). For each test case:
The first part: two integer N, M, indicating the size of the matrix.
The second part: a matrix composed by letter 'A','B','C'.
1<=N, M<=2000.
Output
For each case, output the maximum area of sub-matrix S and sub-matrix D respectively.
Sample Input
3
3 6
CCCCCB
CAAACB
CCCCCB
2 2
AA
CC
3 5
CCCBB
CBCBB
CCCAA
Sample Output
15 3
2 0
3 4
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.3ms with 1 query(s).