#P1913. L 国的战斗之伞兵

L 国的战斗之伞兵

题目背景

L 国即将与 I 国发动战争!!

为了在敌国渗透作战,指挥官决定:派出伞兵前往敌国!然而敌国的风十分强烈,能让伞兵在同一高度不停转悠,直到被刮到一个无风区……(可怜的小兵)

题目描述

I 国的领土是一个 n×mn \times m 的矩形,每个格子都有自己的风向。

当一个伞兵位于从某个格子时,根据该格子上的风向描述符,某些事情将会发生:

风向描述符 将会发生的事情
u 伞兵向上移动一格
d 伞兵向下移动一格
l 伞兵向左移动一格
r 伞兵向右移动一格
o 伞兵空降成功
x 伞兵空降失败

我们默认 I 国领土以外区域的风向描述符均为 x

现在,指挥官在 n×mn \times m 个格子上各投放了一个伞兵,问最终有多少个伞兵空降成功(也就是说,在经过有限次移动后能够来到一个风向描述符为 o 的格子)。

输入格式

第一行两个正整数 n,m (1n,m1000)n,m\ (1 \leq n,m \leq 1000)

以下 nn 行,每行 mm 个字符,表示每个格子的风向描述符。

保证输入中只会出现 u/d/l/r/o,不会出现 x

输出格式

一个数:表示有几个点可以放下伞兵。

5 5
rrrrr
rdddr
rroll
uuuuu
uuuuu

19

提示

样例解释:

投放于第一行的 55 个伞兵最终会移动到 I 国领土以外的区域,因此空降失败。

投放于第二行第五列的 11 个伞兵同理。

剩下的 5×551=195 \times 5-5-1=19 个伞兵都能成功空降。