COCI '21 Contest 5 #2 Dijamant

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 512M

Problem types

Lovro has a table of $n$ $n$ rows and $m$ $m$ columns, where each cell is either . or #. By rotating a square by $45^\circ$ $45^{\circ}$ 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.

Input Specification

The first line contains positive integers $n$ $n$ and $m$ $m$ $(1 \le n, m \le 2\,000)$ $(1 \leq n, m \leq 2 000)$ , the number of rows and columns.

Each of the next $n$ $n$ lines contains $m$ $m$ characters . or # which describe the table.

Output Specification

In the only line print the number of diamonds in the table.

Constraints

Subtask	Points	Constraints
$1$ $1$	$20$ $20$	$1 \le n, m \le 100$ $1 \leq n, m \leq 100$
$2$ $2$	$50$ $50$	No additional constraints.

Sample Input 1

Copy

7 25
.#...#....#....#.....#...
#.#..#...#.#...#....#.#..
.#...#..#...#..#...#...#.
.....#...#.#...#..#.....#
.....#....#....#...#...#.
.....#.........#....#.#..
.....#.........#.....#...

Sample Output 1

Copy

Sample Input 2

Copy

11 17
.....#........#..
....#.#........#.
...#...#....#...#
..#.....#....#.#.
.#....#..#....#..
#....#.#..#......
.#....#..#.......
..#.....#........
...#...#.........
....#.#..........
.....#...........

Sample Output 2

Copy

Explanation for Sample Output 2

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.

Sample Input 3

Copy

5 11
##.#.#.#.##
#.#.#.#.#.#
.#.#.#.#.#.
#.#.#.#.#.#
##.#.#.#.##

Sample Output 3

Copy

Comments

1

quandeptrai123 commented on Nov. 17, 2024, 2:44 a.m.

are there any problems that similar to this?

2

d commented on Nov. 17, 2024, 4:40 a.m.

here's a similar problem: https://dmoj.ca/problem/wac2p3