[Home|Training|Problems|Contests|C Language] | [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 |