시간 제한메모리 제한제출정답맞힌 사람정답 비율
서브태스크 참고 (추가 시간 없음) 1024 MB123233.333%

문제

You are given a rectangular grid with N rows and M columns. Each cell of this grid is painted with one of two colors: green and white. Your task is to find the number of green cells in the largest Christmas tree in this grid.

To define a Christmas tree, first we define a good triangle as follows:

A good triangle with top point at row R, column C and height h is an isoceles triangle consisting entirely of green cells and pointing upward. Formally, this means that: The cell (R, C) is green, and for each i from 0 to h-1 inclusive, the cells in row R+i from column C-i to column C+i are all green.

For example:

..#..
.####
#####

is a good triangle with height 3. The # cells are green and the . cells are white. Note that there is a green cell that is not part of the good triangle, even though it touches the good triangle.

..#..
.###.
####.

is NOT a good triangle, because the 5th cell in the 3rd row is white. However, there are good triangles with height 2 present.

...#.
.###.
#####.

is NOT a good triangle. However, there are good triangles with height 2 present.

A K-Christmas tree is defined as follows:

  • It contains exactly K good triangles in vertical arrangement.
  • The top cell of the i+1-th triangle must share its top edge with the bottom edge of any one of the cells at the base of the i-th triangle. This means that, if the base of the i-th triangle is at row r, from column c1 to column c2, then the top of the i+1-th triangle must be on row r+1, in a column somewhere between c1 and c2, inclusive.

For example, if K = 2:

...#...
..###..
.#####.
#######
..#....
.###...
#####..

is a valid 2-Christmas tree. Note that the height of the 2 good triangles can be different.

..#..
.###.
.#...

is also a valid 2-Christmas tree. Note that a good triangle can be of height 1 and have only one green cell.

...#...
..###..
.#####.
.......
..#....
.###...
#####..

is NOT a valid Christmas tree, because the 2nd triangle must starts from the 4-th row.

...#.
..###
.#...
###..

is NOT a valid Christmas tree, because the top of the 2nd triangle must be in a column between 3 and 5, inclusive.

You need to find the K-Christmas tree with the largest number of green cells.

입력

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of three lines:

  • The first line contains 3 space-separated integers N, M and K, where N is the number of rows of the grid, M is the number of columns of the grid and K is the number of good triangle in the desired Christmas tree.
  • The next N lines each contain exactly M characters. Each character will be either . or #, representing a white or green cell, respectively.

출력

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of green cells in the largest K-Christmas tree. If there is no K-Christmas tree, output 0.

제한

  • 1 ≤ T ≤ 100.
  • 1 ≤ M ≤ 100.
  • 1 ≤ N ≤ 100.
  • Each cell in the grid is either . or #.

Test Set 1 (11점)

시간 제한: 30 초

  • K = 1.

Test Set 2 (32점)

시간 제한: 80 초

  • 1 ≤ K ≤ 100.

예제 입력 1

4
3 5 1
..#..
.###.
#####
3 5 1
.....
.....
.....
4 5 1
#####
#####
#####
#####
4 5 2
#####
#####
#####
#####

예제 출력 1

Case #1: 9
Case #2: 0
Case #3: 9
Case #4: 10

힌트

In sample case #1, the largest 1-Christmas tree has 9 green cells:

..#..
.###.
#####

In sample case #2, there is no 1-Christmas tree.

In sample case #3, one largest 1-Christmas tree with 9 green cells is:

#####
#####
#####
#####

In sample case #4, one largest 2-Christmas tree with 10 green cells is:

#####
#####
#####
#####

채점 및 기타 정보

  • 예제는 채점하지 않는다.