← 返回题目列表

Codeforces · 89/C

C. 筹码游戏

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

让我们考虑下面的游戏。我们有一个大小为 n × m 的矩形场。场地的某些方格包含筹码。

每个芯片上都画有一个箭头。因此,场上的每个筹码都指向以下方向之一:上、下、左或右。

玩家可以选择一个筹码并用它进行移动。

该移动是以下操作序列。所选芯片被标记为当前芯片。之后玩家检查是否还有与当前筹码相同行(或同一列)的筹码,即当前筹码上的箭头所指的筹码。如果至少有一个筹码,则将其中最接近的筹码标记为新的当前筹码,并将前一个当前筹码从场中移除。之后重复检查。这个过程可以重复几次。如果没有找到新的筹码,则当前筹码将从场上移除并且玩家的移动结束。

移动结束时,玩家获得的分数等于删除的筹码数。

通过给定的初始筹码排列,确定玩家在一次移动过程中可以获得的最大点数。还要确定此类移动的次数。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m, n × m ≤ 5000)。然后n行,每行包含m个字符——这就是游戏字段描述。 “。”意味着这个方格是空的。 “L”、“R”、“U”、“D”表示该方块包含一个筹码,其上的箭头对应表示左、右、上、下。

保证一个字段至少有一个芯片。

输出

打印两个数字——玩家在一次移动后可以获得的最大点数以及允许获得该最大点数的移动次数。

示例

输入 #1

4 4
DRLD
U.UL
.UUR
RDDL

输出 #1

10 1

输入 #2

3 5
.D...
RRRLL
.U...

输出 #2

6 2

注意

在第一个样本中,位置 (3, 3) 的筹码获得最大点数。您可以通过下图看到其进度:

所有其他筹码获得的积分较少。