103002: [Atcoder]ABC300 C - Cross

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 column 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

题目描述

我们有一个网格，其中包含$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]$为.。

$(4n+1)$个正方形，由$(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)$组成，当且仅当满足以下所有条件时，称为以$(a,b)$为中心的大小为$n$的十字形：

• $C[a]$是#。
• 对于使得$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]$是.。

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