Problem Description

There are several 'diamonds' placed on a table.

When a square is rotated by $45^\circ$, it forms the shape of a 'diamond'. A 'diamond' is defined as a figure that resembles a 'diamond' shape with its outer border consisting of $\texttt{\#}$ and its interior consisting of $\texttt{.}$.

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$ and $m$, representing the size of the table.

The following $n$ lines each contain $m$ characters, either $\texttt{\#}$ or $\texttt{.}$, representing the table.

Output Format

The number of 'diamonds'.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3

Sample Input #2

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

Sample Output #2

1

Sample Input #3

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

Sample Output #3

14

Notes

[Sample 2 Explanation]

It may appear as if there are three, but in fact, two 'diamonds' are overlapping, which does not meet the definition of having an outer border of $\texttt{\#}$ and an interior of $\texttt{.}$. Therefore, there is only one 'diamond'.

[Data Range and Constraints]

This problem is group-bundled.

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

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

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

见题面 Input 部分

见题面 Output 部分