十字

题目描述

我们有一个 $H$ 行、$W$ 列的网格。用 $(i, j)$ 表示网格中从上数第 $i$ 行、从左数第 $j$ 列的格子。

每个格子中写有符号 # 或 .。设 $C[i][j]$ 为写在 $(i,j)$ 上的字符。对于至少不满足 $1 \leq i \leq H$ 与 $1 \leq j \leq W$ 中某一项的整数 $i$、$j$,定义 $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]$ 中至少有一个为 .。

网格中包含若干个十字。除组成十字的格子外,没有任何格子上写有 #。

此外,属于不同十字的两个格子不会共用一个角。输入中不会给出属于不同十字的格子共用一个角的网格。

设 $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

如题目描述所述,存在一个以 $(2, 2)$ 为中心、大小为 $1$ 的十字,以及一个以 $(3, 7)$ 为中心、大小为 $2$ 的十字。

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$ 为整数。