Cross

题目描述

我们有一个有 $H$ 行水平行和 $W$ 列垂直列的网格。我们用 $(i, j)$ 表示网格中从上数第 $i$ 行、从左数第 $j$ 列的格子。
网格中的每个格子上都写有符号 # 或 $.$。令 $C[i][j]$ 为写在 $(i, j)$ 上的字符。对于整数 $i$ 和 $j$，若至少有一个不满足 $1 \leq i \leq H$ 或 $1 \leq j \leq W$，我们将 $C[i][j]$ 定义为 $.$。
由 $(a, b)$ 以及 $(a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d)$ $(1 \leq d \leq n, 1 \leq n)$ 组成的 $(4n+1)$ 个方格，当且仅当满足以下所有条件时，被称为以 $(a,b)$ 为中心的大小为 $n$ 的十字架：

$C[a][b]$ 是 #。 对于所有满足 $1 \leq d \leq n$ 的整数 $d$，$C[a+d][b+d],C[a+d][b-d],C[a-d][b+d]$ 和 $C[a-d][b-d]$ 全部是 #， 至少有一个 $C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1]$ 和 $C[a-n-1][b-n-1]$ 是 $.$。

例如，下图中的网格在 $(2, 2)$ 处有一个大小为 $1$ 的十字架，在 $(3, 7)$ 处有一个大小为 $2$ 的十字架。 网格中有一些十字架。除了组成十字架的那些格子之外，其他格子上没有 #。
此外，组成两个不同十字架的格子之间没有两个格子共享一个角。下图中的两个网格是组成不同十字架的两个格子共享角的示例；这样的网格不会作为输入给出。例如，左边的网格是无效的，因为 $(3, 3)$ 和 $(4, 4)$ 共享一个角。 令 $N = \min(H, W)$，并且 $S_n$ 为大小为 $n$ 的十字架的数量。求 $S_1, S_2, \dots, S_N$。

输入格式

输入从标准输入按以下格式给出： $H$ $W$ $C[1][1]C[1][2]\dots C[1][W]$ $C[2][1]C[2][2]\dots C[2][W]$ $\vdots$ $C[H][1]C[H][2]\dots C[H][W]$

输出格式

输出 $S_1, S_2, \dots,$ 和 $S_N$，用空格分隔。

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

1 1 0 0 0

3 3
...
...
...

0 0 0

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

3 0 0

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0

提示

$3 \leq H, W \leq 100$ $C[i][j]$ 是 # 或 $.$。 组成两个不同十字架的两个不同方格之间没有两个方格共享一个角。 $H$ 和 $W$ 为整数。如问题描述，在 $(2, 2)$ 处有一个大小为 $1$ 的十字架，在 $(3, 7)$ 处有一个大小为 $2$ 的十字架。
也可能没有十字架。

标签: AtCoder|abc300C

来源

AtCoder|abc300C