| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 18 | 9 | 9 | 52.941% |
Lovro has a table of $n$ rows and $m$ columns, where each cell is either . or #. By rotating a square by 45◦ a diamond shape is formed in the table. For a part of the table to be considered a diamond, its edge must also consist only of the character #, while its inside must be completely filled with . and it must be nonempty. Outside of a diamond any character is allowed. Diamonds come in different sizes, and the three smallest examples of a diamond are shown in the first sample.
Fabijan asked Lovro to tell him how many diamonds are there in the table, or else Lovro has to give him a cookie. Help Lovro by writing a program which counts the number of diamonds in his table.
The first line contains positive integers $n$ and $m$ (1ドル ≤ n, m ≤ 2000$), the number of rows and columns. Each of the next $n$ lines contains $m$ characters . or # which describe the table.
In the only line print the number of diamonds in the table.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | 1ドル ≤ n, m ≤ 100$ |
| 2 | 50 | No additional constraints. |
7 25 .#...#....#....#.....#... #.#..#...#.#...#....#.#.. .#...#..#...#..#...#...#. .....#...#.#...#..#.....# .....#....#....#...#...#. .....#.........#....#.#.. .....#.........#.....#...
3
11 17 .....#........#.. ....#.#........#. ...#...#....#...# ..#.....#....#.#. .#....#..#....#.. #....#.#..#...... .#....#..#....... ..#.....#........ ...#...#......... ....#.#.......... .....#...........
1
5 11 ##.#.#.#.## #.#.#.#.#.# .#.#.#.#.#. #.#.#.#.#.# ##.#.#.#.##
14
Clarification of the second example:
There is only one diamond in the table (the one with the smallest possible size). There appears to be another diamond containing it, but it is not considered a diamond because its inside is not completely filled with '.'. The shape on the right side of the table is also not a diamond because it’s missing a # character on its edge.