P8325 [COCI 2021/2022 #5] Dijamant

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.

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.

The number of “diamonds”.

**[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](https://hsin.hr/coci/contest5_tasks.pdf) Task 2 Dijamant. Translated by ChatGPT 5