← 返回题目列表

Codeforces · 436/B

B. Om Nom 和蜘蛛

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

Om Nom 非常喜欢糖果,但不喜欢蜘蛛,因为它们经常偷糖果。有一天,Om Nom 想去公园散步。不幸的是,公园里有一些蜘蛛,Om Nom 根本不想看到它们。

公园可以表示为一个 n × m 的矩形场地。公园里有 k 只蜘蛛,每只蜘蛛在时间 0 时都在场地的某个单元格中。蜘蛛一直在移动,并且每只蜘蛛总是沿着四个方向之一移动(左、右、下、上)。在一个单位时间内,一只蜘蛛从自己的单元格中沿着相应的方向爬​​行到旁边相邻的单元格中。如果给定方向上没有单元格,那么蜘蛛就会离开公园。蜘蛛在移动时不会互相干扰。具体来说,一个细胞可以同时拥有多个蜘蛛。

Om Nom 还不确定从哪里开始步行,但他肯定想要:

- 在时间 0 处开始在田地的上排单元格行走(保证该行单元格不包含任何蜘蛛);
- 沿着场地向最低行移动(当 Om Nom 离开公园边界时步行结束)。

我们知道 Om Nom 通过跳跃来移动。一次跳跃需要一个时间单位,并将小怪物从他的牢房运送到下排的侧面相邻牢房或公园边界外。

每次 Om Nom 降落在牢房中时,他都会看到此时来到该牢房的所有蜘蛛。 Om Nom 想要选择最佳的单元格来开始步行。这就是为什么他想知道:对于每个可能的起始单元,如果他从这个单元出发,在步行过程中他会看到多少只蜘蛛?帮助他计算每个可能的起始单元格所需的值。

输入

第一行包含三个整数 n、m、k (2 ≤ n, m ≤ 2000; 0 ≤ k ≤ m(n - 1))。

接下来的 n 行每行包含 m 个字符——公园的描述。第 i 行中的字符描述了公园场地的第 i 行。如果该行中的字符等于“.”,则表示该字段对应的单元格为空;否则,该行中的字符将等于以下四个字符之一:“L”(表示该单元格在时间 0 处有一只蜘蛛,向左移动)、“R”(向右移动的蜘蛛)、“U”(向上移动的蜘蛛)、“D”(向下移动的蜘蛛)。

保证第一行不包含任何蜘蛛。保证字段的描述不包含多余的字符。保证在时间 0 时该字段恰好包含 k 个蜘蛛。

输出

打印 m 个整数:第 j 个整数必须显示 Om Nom 从第一行的第 j 个单元格开始行走时将看到的蜘蛛数量。该字段中任意行中的单元格均从左到右编号。

示例

输入 #1

3 3 4
...
R.L
R.U

输出 #1

0 2 2

输入 #2

2 2 2
..
RL

输出 #2

1 1

输入 #3

2 2 2
..
LR

输出 #3

0 0

输入#4

3 4 8
....
RRLL
UUUU

输出#4

1 3 3 1

输入 #5

2 2 2
..
UU

输出 #5

0 0

注意

考虑第一个样本。下面的注释显示了蜘蛛在场地上的排列如何随着时间的推移而变化:

字符“*”代表同时包含两只蜘蛛的单元格。

- 如果 Om Nom 从第一行的第一个单元格开始,他将不会看到任何蜘蛛。
- 如果他从第二个单元格开始,他会在时间 1 看到两只蜘蛛。
- 如果他从第三个单元格开始,他会看到两只蜘蛛:一只在时间 1,另一只在时间 2。