Problem Description

Several “diamonds” are placed on the table.

When a square is rotated by $45^\circ$, it forms a “rhombus” shape. A shape whose outline looks like a “rhombus”, with the entire outer border made of $\texttt \#$ and the entire interior made of $\texttt .$ is defined as one “diamond”.

Given a table of size $n \times m$, count how many “diamonds” are placed on the table.

Input Format

The first line contains two positive integers $n, m$, representing the size of the table.

The next $n$ lines each contain $m$ characters $\texttt \#$ or $\texttt .$ , representing the table.

Output Format

The number of “diamonds”.

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

3

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

1

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

14

Hint

[Sample 2 Explanation]

It looks like there are $3$ diamonds, but in fact two “rhombuses” contain each other, so they do not meet the definition “outer border is all $\texttt \#$ but the interior is all $\texttt .$”. Therefore, there is only $1$ diamond.

[Constraints and Notes]

This problem uses bundled tests.

• Subtask 1 (20 pts): $1 \le n, m \le 100$.
• Subtask 2 (50 pts): no special restrictions.

For $100\%$ of the testdata, $1 \le n, m \le 2000$.

[Source] COCI 2021-2022#5 Task 2 Dijamant.

Translated by ChatGPT 5