시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
서브태스크 참고 (추가 시간 없음) | 1024 MB | 7 | 3 | 2 | 33.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:
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:
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.
.
or #
.시간 제한: 30 초
시간 제한: 80 초
4 3 5 1 ..#.. .###. ##### 3 5 1 ..... ..... ..... 4 5 1 ##### ##### ##### ##### 4 5 2 ##### ##### ##### #####
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:
#####
#####
#####
#####
Contest > Google > Kick Start > Google Kick Start 2017 > Round B C번