障害物競走

2 secs 1024 MB
wisteriahuman's icon wisteriahuman
Tweet
問題
提出
テストケース
解説

問題文

あなたは障害物競走の選手です。
目の前には NN 本のレーンがあります。
各レーンには LL 個の区間があり、いくつかの区間には障害物が待ち構えています。 11 つの区間の障害物を通過するのにあなたは時間 TT を要します。
各レーンの障害物情報は LL 個の長さ NN の文字列 S1,S2,…,SLS_1,S_2,\dots,S_L として与えられ、 ii 本目のレーンの区間 jj に障害物がある場合、Sj(1≤j≤L)S_j (1 \le j \le L) の i(1≤i≤N)i (1 \le i \le N) 文字目は # で、障害物がない場合は .です。
あなたが各レーンを走り終えるのに必要な時間を計算し、それぞれ出力してください。

制約

  • 1≤N,L≤10001 \le N,L \le 1000
  • 1≤T≤1051 \le T \le 10^5
  • N,L,TN,L,T は全て整数
  • Si(1≤i≤L)S_i (1 \le i \le L) の j(1≤j≤N)j (1 \le j \le N) 文字目は # または . のいずれかです。

入力

入力は次の形式で与えられます。

N L TN ~ L ~ T
S1S_1
S2S_2
⋮\vdots
SLS_L

出力

あなたが各レーンを走り終えるのに必要な時間を計算し、結果を次の形式で出力してください。

  • 各レーンを走り終えるのにかかる時間を NN 本のレーンに対して、11 本目から順に出力してください。
  • 各時間（レーンごとの所要時間）はスペースで区切って表示してください。
  • 最後に改行を入れてください。

出力形式は以下の通りです。

A1 A2 A3 … ANA_1 ~ A_2 ~ A_3 ~ \ldots ~ A_N

入力例 11

3 4 5
..#
###
...
#.#

出力例 11

10 5 15

sample1

  • 11 本目のレーンには、区間 22 、区間 44 に合計 22 つの障害物があるので、走り終えるのに必要な時間は 1010 です。
  • 22 本目のレーンには、区間 22 に 11 つの障害物があるので、走り終えるのに必要な時間は 55 です。
  • 33 本目のレーンには、区間 11 、区間 22 、区間 44 に合計 33 つの障害物があるので、走り終えるのに必要な時間は 1515 です。

入力例 22

5 5 7
..#..
##..#
.#..#
.#.#.
..##.

出力例 22

7 21 14 14 14

入力例 33

35 21 299
.....#............#................
....####........####...............
...##################..............
..####################.............
.######################............
.######################............
.######################............
.######################............
..####################.............
....################...............
....################...............
...##################..............
..####################.........###.
..####################......#######
.######################....####....
########################..####.....
########################..###......
########################.####......
.###########################.......
..########################.........
.....#################.............

出力例 33

897 2691 4186 4784 5681 6279 5980 5980 5681 5681 5681 5681 5681 5681 5681 5681 5980 5980 6279 5980 5083 4485 2990 1495 598 897 1196 1495 1495 897 598 598 598 598 299

提出

Go (1.21)