Score : $300$ points

问题描述

我们有一个由 $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, b)$、$(a+d,b+d)$、$(a+d,b-d)$、$(a-d,b+d)$ 和 $(a-d,b-d)$ 这 $(4n+1)$ 个格子（其中 $1 \leq d \leq n$，$1 \leq n$）是一个 大小为 $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]$ 是 .。

例如，下图所示网格中有一个大小为 $1$ 的十字交叉点，中心位于 $(2, 2)$，另一个大小为 $2$ 的十字交叉点中心位于 $(3, 7)$。

网格中有一些十字交叉点。除了构成交叉点的格子外，其它格子上未写有 #。
另外，两个不同交叉点所包含的方格之间不会共享一个角。下图所示的两个网格是两个不同交叉点所包含的方格共享一个角的例子；这样的网格不会作为输入给出。例如，左边的网格无效，因为 $(3, 3)$ 和 $(4, 4)$ 共享了一个角。

令 $N = \min(H, W)$，并令 $S_n$ 表示大小为 $n$ 的十字交叉点的数量。求解 $S_1, S_2, \dots, S_N$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have a grid with $H$ horizontal rows and $W$ vertical columns. We denote by $(i, j)$ the cell at the $i$-th row from the top and $j$-th column from the left of the grid.
Each cell in the grid has a symbol # or . written on it. Let $C[i][j]$ be the character written on $(i, j)$. For integers $i$ and $j$ such that at least one of $1 \leq i \leq H$ and $1 \leq j \leq W$ is violated, we define $C[i][j]$ to be ..

$(4n+1)$ squares, consisting of $(a, b)$ and $(a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d)$ $(1 \leq d \leq n, 1 \leq n)$, are said to be a cross of size $n$ centered at $(a,b)$ if and only if all of the following conditions are satisfied:

• $C[a][b]$ is #.
• $C[a+d][b+d],C[a+d][b-d],C[a-d][b+d]$, and $C[a-d][b-d]$ are all #, for all integers $d$ such that $1 \leq d \leq n$,
• At least one of $C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1]$, and $C[a-n-1][b-n-1]$ is ..

For example, the grid in the following figure has a cross of size $1$ centered at $(2, 2)$ and another of size $2$ centered at $(3, 7)$.

The grid has some crosses. No # is written on the cells except for those comprising a cross.
Additionally, no two squares that comprise two different crosses share a corner. The two grids in the following figure are the examples of grids where two squares that comprise different crosses share a corner; such grids are not given as an input. For example, the left grid is invalid because $(3, 3)$ and $(4, 4)$ share a corner.

Let $N = \min(H, W)$, and $S_n$ be the number of crosses of size $n$. Find $S_1, S_2, \dots, S_N$.

Constraints

• $3 \leq H, W \leq 100$
• $C[i][j]$ is # or ..
• No two different squares that comprise two different crosses share a corner.
• $H$ and $W$ are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print $S_1, S_2, \dots$, and $S_N$, separated by spaces.

Sample Input 1

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

Sample Output 1

1 1 0 0 0

As described in the Problem Statement, there are a cross of size $1$ centered at $(2, 2)$ and another of size $2$ centered at $(3, 7)$.

Sample Input 2

3 3
...
...
...

Sample Output 2

0 0 0

There may be no cross.

Sample Input 3

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

Sample Output 3

3 0 0

Sample Input 4

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

Sample Output 4

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

update @ 2024/3/10 08:24:10