|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|60 초 (추가 시간 없음)||1024 MB (추가 메모리 없음)||32||26||23||82.143%|
Given a grid of R rows and C columns each cell in the grid is either 0 or 1.
A segment is a nonempty sequence of consecutive cells such that all cells are in the same row or the same column. We define the length of a segment as number of cells in the sequence.
A segment is called "good" if all the cells in the segment contain only 1s.
An "L-shape" is defined as an unordered pair of segments, which has all the following properties:
We need to count the number of L-shapes in the grid.
Below you can find two examples of correct L-shapes,
and three examples of invalid L-shapes.
Note that in the shape on the left, two segments do not share a common endpoint. The next two shapes do not meet the last requirement, as in the middle shape both segments have the same length, and in the last shape the longer segment is longer than twice the length of the shorter one.
The first line of the input contains the number of test cases, T. T test cases follow.
The first line of each testcase contains two integers R and C.
Then, R lines follow, each line with C integers representing the cells of the grid.
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 L-shapes.
2 4 3 1 0 0 1 0 1 1 0 0 1 1 0 6 4 1 0 0 0 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0
Case #1: 1 Case #2: 9
In Sample Case #1, there is one L-shape.
In Sample Case #2, there are nine L-shapes.
The first three L-shapes are shown on the picture below.