题目要求统计每个空地格子被多少盏灯照到。
一盏灯的传播过程是完全确定的:
#、或者是另一盏灯 L/R/U/D,则传播停止。给定一个 n 行 m 列的网格地图,每个格子是以下字符之一:
'#':障碍物;
'.':空地;
'/'、' \ ':镜子;
'L'、'R'、'U'、'D':一盏灯,分别表示它只会向左/右/上/下照射。
灯光传播规则如下:
一盏灯从自身的格子出发,只沿着当前方向,一格一格向前传播;
如果灯光向前进入的下一个格子是障碍物或另一盏灯,那么灯光会在进入前停止(也就是说,障碍物和灯格子都不会被照亮,也不会被灯光穿过);
一盏灯光进入了镜子格子,那么它会立刻改变方向:进入 '/' 时,'L'→'D'、'R'→'U'、'U'→'R'、'D'→'L';进入 ' \ ' 时,'L'→'U'、'R'→'D'、'U'→'L'、'D'→'R';
镜子格子不是空地,因此不计入光照强度,但灯光可以进入镜子格子并继续传播。
对于每一个空地格子,它的光照强度等于能照到它的灯的数量(每盏灯最多贡献 1)。你需要输出地图中每个格子的光照强度。
第一行输入两个整数 n 和 m(1≤n≤104,1≤m≤104,1≤n×m≤104),表示地图大小
此后 n 行,第 i 行输入一个长度为 m 的字符串 si。保证 si 仅由 '#'、'.'、'/'、' \ '、'L'、'R'、'U'、'D' 组成,并且地图中镜子格子(即 '/' 或 ' \ ')的总数不超过 5,灯光格子的总数不超过 3×103。
输出 n 行,每行输出 m 个整数,整数之间用单个空格分隔:
若该格子是障碍物、镜子或灯,输出 −1;
若该格子是空地,输出它的光照强度。
输入
3 4
R.#.
..#.
.L..
输出
-1 1 -1 0
0 0 -1 0
1 -1 0 0
说明
在这个样例中:
第 1 行第 2 列是空地,它能被第 1 行第 1 列的 'R' 灯照到,所以输出 1;
第 3 行第 1 列是空地,它能被第 3 行第 3 列的 'L' 灯照到,所以输出 1;
所有灯格子与障碍物格子都输出 −1。
输入
4 4
R/L.
....
R...
....
输出
-1 -1 -1 0
0 1 0 0
-1 2 1 1
0 1 0 0