Om Nom and Spiders

题意翻译

## 题目描述 奥姆诺姆真的很喜欢糖果，但他不喜欢蜘蛛，因为它们经常偷糖果。有一天，奥姆诺姆想去公园散步。不幸的是，公园里有一些蜘蛛，奥姆诺姆根本不想看到它们。 公园可以用一个n×m的矩形表示。公园里有k蜘蛛，每只蜘蛛在0点的时候都是在田野的某个牢房里。蜘蛛一直在移动，每个蜘蛛总是朝四个方向之一移动（左、右、下、上）。在一个时间单位内，一只蜘蛛从他的牢房向相应方向爬到相邻的一侧牢房。如果在指定的方向没有牢房，蜘蛛就会离开公园。蜘蛛在移动时不会互相干扰。具体来说，一个牢房可以同时有多个蜘蛛。 奥姆诺姆还不确定从哪里开始他的步行，但他肯定想要： - 在时间为0时开始在田野的上行处行走（保证该行单元格中不包含任何蜘蛛）； - 沿着田野向最下面一排走去（当奥姆诺姆离开公园边界时，步行结束）。 我们知道奥姆诺姆是通过跳跃来移动的。奥姆诺姆一次跳跃需要一个时间单位，小怪兽会从他的牢房到另一边相邻牢房的下一行或公园边界外。 每次Om Nom降落在一个牢房里，他都会看到此时此刻所有来到牢房的蜘蛛。omnom想要选择一个最佳的单元来开始漫游。为什么每次他都会从牢房开始走呢？帮助他计算每个可能的启动单元所需的值。 ## 输入格式 第一行包含三个整数n，m,k(2<=n,m<=2000;0<=k<=m(n-1)) 接下来的n行每行包含m个字符-公园的描述。第二行的字符描述了公园的第二行。如果行中的字符为“.”，则表示字段对应的单元格为空；否则，行中的字符将为以下四个字符之一：“L”（表示此单元格在时间0处有一个蜘蛛，向左移动）、“R”（向右移动的蜘蛛）、“U”（向上移动的蜘蛛）、“D”（向下移动的蜘蛛）。 可以保证第一行不包含任何蜘蛛。保证字段的描述不包含额外字符。可以保证在时间0时，该字段正好包含k只蜘蛛 ## 输出格式 打印m个整数：第j个整数必须显示从第一行的第j个单元格开始行走的蜘蛛的数目。田野中任何行中的单元格都是从左到右编号的。

题目描述

Om Nom really likes candies and doesn't like spiders as they frequently steal candies. One day Om Nom fancied a walk in a park. Unfortunately, the park has some spiders and Om Nom doesn't want to see them at all. The park can be represented as a rectangular $ n×m $ field. The park has $ k $ spiders, each spider at time 0 is at some cell of the field. The spiders move all the time, and each spider always moves in one of the four directions (left, right, down, up). In a unit of time, a spider crawls from his cell to the side-adjacent cell in the corresponding direction. If there is no cell in the given direction, then the spider leaves the park. The spiders do not interfere with each other as they move. Specifically, one cell can have multiple spiders at the same time. Om Nom isn't yet sure where to start his walk from but he definitely wants: - to start walking at time 0 at an upper row cell of the field (it is guaranteed that the cells in this row do not contain any spiders); - to walk by moving down the field towards the lowest row (the walk ends when Om Nom leaves the boundaries of the park). We know that Om Nom moves by jumping. One jump takes one time unit and transports the little monster from his cell to either a side-adjacent cell on the lower row or outside the park boundaries. Each time Om Nom lands in a cell he sees all the spiders that have come to that cell at this moment of time. Om Nom wants to choose the optimal cell to start the walk from. That's why he wonders: for each possible starting cell, how many spiders will he see during the walk if he starts from this cell? Help him and calculate the required value for each possible starting cell.

输入输出格式

输入格式

The first line contains three integers $ n,m,k $ $ (2<=n,m<=2000; 0<=k<=m(n-1)) $ . Each of the next $ n $ lines contains $ m $ characters — the description of the park. The characters in the $ i $ -th line describe the $ i $ -th row of the park field. If the character in the line equals ".", that means that the corresponding cell of the field is empty; otherwise, the character in the line will equal one of the four characters: "L" (meaning that this cell has a spider at time 0, moving left), "R" (a spider moving right), "U" (a spider moving up), "D" (a spider moving down). It is guaranteed that the first row doesn't contain any spiders. It is guaranteed that the description of the field contains no extra characters. It is guaranteed that at time 0 the field contains exactly $ k $ spiders.

输出格式

Print $ m $ integers: the $ j $ -th integer must show the number of spiders Om Nom will see if he starts his walk from the $ j $ -th cell of the first row. The cells in any row of the field are numbered from left to right.

输入输出样例

输入样例 #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 

说明

Consider the first sample. The notes below show how the spider arrangement changes on the field over time: `<br></br>... ... ..U ...<br></br>R.L -> .*U -> L.R -> ...<br></br>R.U .R. ..R ...<br></br><br></br>`Character "\*" represents a cell that contains two spiders at the same time. - If Om Nom starts from the first cell of the first row, he won't see any spiders. - If he starts from the second cell, he will see two spiders at time 1. - If he starts from the third cell, he will see two spiders: one at time 1, the other one at time 2.