分数: 4 点
问题陈述
你被给予 N \times N 网格。让 (i,j) 表示单元格 i从顶部算起的第行和 j左起第 列。
每个单元格的状态由下式描述 N 字符串 S_1, S_2, \dots, S_N,每个长度 N.
如果
您打印的 j- 第一个字符 S_i is @,然后是单元格 (i,j) 包含一枚硬币。如果是的话 .,则单元格为空。
您从单元格开始 (1,1)。可以保证 (1,1) 为空。
您可以执行以下操作任意次数(包括零次):
- 让您当前的位置为 (i,j)。移至右侧单元格 (i,j+1) 或下单元格 (i+1,j)。你不能移动到网格之外。如果目标单元格中有一枚硬币,您必须捡起它。
对于每个 x = 0, 1, \dots, 2N-2,解决以下问题:
- 执行一些操作(可能为零)后,您到达一个单元格 (i,j) 同时具有 x 硬币。有多少个可能的细胞 (i,j) 有吗?
约束
- 2 \leq N \leq 4000
- S_1, S_2, \dots, S_N 是长度的字符串 N 组成
@和. - 第一个字符 S_1 is
. - N 是一个整数
部分分数
该问题得分不全。
- 如果您使用以下方法求解数据集 N \leq 1500,你会得到 2 点。
输入
输入由标准输入给出,格式如下:
N S_1 S_2 \vdots S_N
输出
打印 2N-1 行。上 i第行,输出答案 x = i-1.
示例输入 1
3 .@@ ..@ @..
示例输出 1
5 6 3 2 0
例如,当 x=0,可能的单元格 (i,j) 是 (1,1), (2,1), (2,2), (3,2), (3,3),所以有 5 这样的细胞。
示例输入 2
7 ...@@@. ..@@@@@ @...@.. ..@..@. .....@@ .@@@@@@ @@.@.@.
示例输出 2
15 29 28 23 19 13 6 5 3 0 0 0 0