← 返回题目列表

AtCoder · ndpc2026_h

H. 硬币

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

分数: 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