← 返回题目列表

AtCoder · abc300_c

E. 十字

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

我们有一个网格 H 水平行和 W 垂直列。我们表示为 (i, j) 的单元格 i从顶部开始的第行和 j- 网格左侧的第列。
网格中的每个单元格都有一个符号 上面写着 # or . 。让 C[i][j] 是写在上面的字符 (i, j)。对于整数 i 和 j 使得至少其中之一 1 \leq i \leq H 和 1 \leq j \leq W 被违反,我们定义 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),据说是 尺寸十字 n 以 (a,b) 当且仅当满足以下所有条件时:

  • C[a][b] is #.
  • C[a+d][b+d],C[a+d][b-d],C[a-d][b+d],和 C[a-d][b-d] 都是 #,对于所有整数 d 这样 1 \leq d \leq n,
  • 至少其中之一 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] is ..

比如下图中的网格有一个大小为的十字 1 以 (2, 2) 和另一个尺寸 2 以 (3, 7).

image

网格有一些十字。否 除包含十字的单元格外,单元格上均写有 # 。
此外,包含两个不同十字的两个正方形不会共享一个角。下图中的两个网格是由不同十字组成的两个正方形共用一个角的网格示例; 此类网格不会作为输入给出。例如,左侧网格无效,因为 (3, 3) 和 (4, 4) 共享一个角落。

image2

让 N = \min(H, W),和 S_n 是大小的十字数 n。查找 S_1, S_2, \dots, S_N.

约束

  • 3 \leq H, W \leq 100
  • C[i][j] is # or ..
  • 包含两个不同十字的两个不同正方形不会共享一个角。
  • H 和 W 是整数。

输入

输入由标准输入按以下格式给出:

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,用空格分隔。


示例输入 1

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

示例输出 1

1 1 0 0 0

如问题陈述中所述,有一个尺寸的十字 1 以 (2, 2) 和另一个尺寸 2 以 (3, 7).


示例输入 2

3 3
...
...
...

示例输出 2

0 0 0

可能没有交叉。


示例输入 3

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

示例输出 3

3 0 0

示例输入 4

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

示例输出 4

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