P8325.md

[COCI2021-2022#5] Dijamant

题目描述

桌上摆放有若干颗『钻石』。

当一个正方形旋转 $45^\circ$ 时，它就形成了『菱形』的形状。规定外形形如『菱形』且外边框均为 $\texttt #$ 但内部均为 $\texttt .$ 的图形为一颗『钻石』。

给定一个 $n \times m$ 大小的桌面，统计桌上摆放有多少颗『钻石』。

输入格式

第一行两个正整数 $n,m$，表示桌面的大小。

接下来的 $n$ 行，每行 $m$ 个字符 $\texttt #$ 或 $\texttt .$，表示桌面。

输出格式

『钻石』的数量。

样例 #1

样例输入 #1

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

样例输出 #1

3

样例 #2

样例输入 #2

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

样例输出 #2

1

样例 #3

样例输入 #3

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

样例输出 #3

14

提示

【样例 2 解释】

看起来好像有 $3$ 颗，但实际上有两个『菱形』互相包含，因此不符合『外边框均为 $\texttt #$ 但内部均为 $\texttt .$』的定义。故只有 $1$ 颗『钻石』。

【数据规模与约定】

本题采用捆绑测试。

• Subtask 1（20 pts）：$1 \le n,m \le 100$。
• Subtask 2（50 pts）：无特殊限制。

对于 $100%$ 的数据，$1 \le n,m \le 2000$。

【来源】COCI 2021-2022#5 Task 2 Dijamant。