H - Coin Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 4 点

問題文

縦横 N マスのグリッドがあります。グリッドの上から i 行目、左から j 列目のマスを (i,j) と呼びます。
グリッドの各マスの状態は N 個の長さ N の文字列 S_1,S_2,\dots,S_N によって表されます。S_i の j 文字目が @ である時は (i,j) はコインが 1 枚落ちているマス、. である時は何もないマスです。
あなたはグリッドの (1,1) にいます。(1,1) は何もないマスであることが保証されています。
あなたは以下の行動を 0 回以上自由な回数行うことができます。

  • 今自分がいるマスを (i,j) とする。右のマスまたは下のマス、すなわち (i,j+1) または (i+1,j) に移動する。グリッドの外への移動はできない。移動した先のマスにコインが落ちていた場合、あなたはそれを必ず拾う。

x = 0, 1, \dots, 2N-2 について次の問題を解いてください。

  • あなたは 0 回以上行動してあるマス (i,j) にたどり着きました。この時、あなたはコインを x 枚持っていました。(i,j) としてあり得るマスは何マスありますか？

制約

  • 2 \leq N \leq 4000
  • S_1, S_2, \dots, S_N は @ と . からなる長さ N の文字列
  • S_1 の 1 文字目は .
  • 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

Score : 4 points

Problem Statement

You are given an N \times N grid. Let (i,j) denote the cell in the i-th row from the top and the j-th column from the left.

The state of each cell is described by N strings S_1, S_2, \dots, S_N, each of length N.
If the j-th character of S_i is @, then cell (i,j) contains one coin. If it is ., then the cell is empty.

You start at cell (1,1). It is guaranteed that (1,1) is empty.

You may perform the following action any number of times (including zero):

  • Let your current position be (i,j). Move to either the right cell (i,j+1) or the down cell (i+1,j). You cannot move outside the grid. If the destination cell contains a coin, you must pick it up.

For each x = 0, 1, \dots, 2N-2, solve the following:

  • After performing some actions (possibly zero), you reach a cell (i,j) while having exactly x coins. How many possible cells (i,j) are there?

Constraints

  • 2 \leq N \leq 4000
  • S_1, S_2, \dots, S_N are strings of length N consisting of @ and .
  • The first character of S_1 is .
  • N is an integer

Partial Score

This problem has partial scoring.

  • If you solve the dataset with N \leq 1500, you will get 2 points.

Input

The input is given from standard input in the following format:

N
S_1
S_2
\vdots
S_N

Output

Print 2N-1 lines. On the i-th line, output the answer for x = i-1.

Sample Input 1

3
.@@
..@
@..

Sample Output 1

5
6
3
2
0

For example, when x=0, the possible cells (i,j) are (1,1), (2,1), (2,2), (3,2), (3,3), so there are 5 such cells.

Sample Input 2

7
...@@@.
..@@@@@
@...@..
..@..@.
.....@@
.@@@@@@
@@.@.@.

Sample Output 2

15
29
28
23
19
13
6
5
3
0
0
0
0