小太阳的帕鲁世界1
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

注意:小太阳的帕鲁世界ⅠⅡⅢ 仅在题目名称及背景有所关系,题目之间并无关系也不与难度挂钩。
小太阳来到了修行者瀑布,传说这里栖息着一只名为云海鹿的帕鲁,可以乘云驾雾,是这片大陆上速度最快的帕鲁,小太阳非常渴望拥有一只属于自己的云海鹿。可是众所周知的是,云海鹿躲藏在山体中的坑道里,坑道的路况太过复杂,小太阳在寻找云海鹿的过程中迷路了!
经过一番波折,小太阳终于逃出了坑道,然而他并不甘心,请你帮助小太阳找到从任意位置出发可以找到云海鹿的最短路径。
你处在一个大小为 n * m 的长方形矩阵上。矩阵的行从上到下编号为 1n ,列从左到右编号为 1m
矩阵的每个单元格上都写有一个符号"L"、"R"、"D"、"U",分别表示进入该单元格的方向必须向左、向右、向下或向上。
即如果当前单元格为 "L" ,你必须从这个单元格右边的格子出发才能到达该单元格。
找到从任意位置出发到达(n,m)的最短路径长度。

输入描述:

第一行包含两个整数 n,m (1 \leq n,m \leq 2000),分别表示矩阵的行数、列数。
接下来 n 行每行包含 m 个字符(仅包含"L"、"R"、"D"、"U"),表示该单元格上的符号。

输出描述:

输出 nm 列整数表示从 (i,j) 到达 (n,m) 的最短路径,若无法到达则输出-1
示例1

输入

复制
1 2
DR

输出

复制
1 0
示例2

输入

复制
1 3
RUR

输出

复制
-1 1 0