English · Original
Chinese · Translation
Formal · Original
Let's consider the following game. We have a rectangular field _n_ × _m_ in size. Some squares of the field contain chips.
Each chip has an arrow painted on it. Thus, each chip on the field points in one of the following directions: up, down, left or right.
The player may choose a chip and make a move with it.
The move is the following sequence of actions. The chosen chip is marked as the current one. After that the player checks whether there are more chips in the same row (or in the same column) with the current one that are pointed by the arrow on the current chip. If there is at least one chip then the closest of them is marked as the new current chip and the former current chip is removed from the field. After that the check is repeated. This process can be repeated several times. If a new chip is not found, then the current chip is removed from the field and the player's move ends.
By the end of a move the player receives several points equal to the number of the deleted chips.
By the given initial chip arrangement determine the maximum number of points that a player can receive during one move. Also determine the number of such moves.
## Input
The first line contains two integers _n_ and _m_ (1 ≤ _n_, _m_, _n_ × _m_ ≤ 5000). Then follow _n_ lines containing _m_ characters each — that is the game field description. "_._" means that this square is empty. "_L_", "_R_", "_U_", "_D_" mean that this square contains a chip and an arrow on it says left, right, up or down correspondingly.
It is guaranteed that a field has at least one chip.
## Output
Print two numbers — the maximal number of points a player can get after a move and the number of moves that allow receiving this maximum number of points.
[samples]
## Note
In the first sample the maximum number of points is earned by the chip in the position (3, 3). You can see its progress at the following picture:
<center></center>All other chips earn fewer points.
让我们考虑以下游戏。我们有一个大小为 #cf_span[n × m] 的矩形棋盘，某些格子上放置了棋子。
每个棋子上都画有一个箭头，因此每个棋子指向以下四个方向之一：上、下、左或右。
玩家可以选择一个棋子并进行一次移动。
移动的流程如下：选定的棋子被标记为当前棋子。接着，玩家检查在当前棋子所在的行（或列）中，是否存在至少一个被当前棋子箭头所指向方向上的其他棋子。如果存在至少一个这样的棋子，则离当前棋子最近的那个被标记为新的当前棋子，而原来的当前棋子从棋盘上移除。然后重复上述检查过程。这个过程可以重复多次。如果没有找到新的棋子，则当前棋子被移除，玩家的移动结束。
在一次移动结束时，玩家获得的分数等于被移除的棋子数量。
给定初始的棋子布局，请确定玩家在一次移动中能获得的最大分数，以及能获得该最大分数的移动方式的数量。
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m, n × m ≤ 5000]）。接下来是 #cf_span[n] 行，每行包含 #cf_span[m] 个字符，表示游戏棋盘的描述。"_._" 表示该格子为空；"_L_"、"_R_"、"_U_"、"_D_" 分别表示该格子包含一个棋子，且其箭头指向左、右、上或下。
保证棋盘上至少有一个棋子。
请输出两个数字——玩家在一次移动中能获得的最大分数，以及能获得该最大分数的移动方式的数量。
在第一个样例中，最大分数由位置为 #cf_span[(3, 3)] 的棋子获得。其移动过程如下图所示：
其他所有棋子获得的分数都更少。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m, n × m ≤ 5000]）。接下来是 #cf_span[n] 行，每行包含 #cf_span[m] 个字符，表示游戏棋盘的描述。"_._" 表示该格子为空；"_L_"、"_R_"、"_U_"、"_D_" 分别表示该格子包含一个棋子，且其箭头指向左、右、上或下。保证棋盘上至少有一个棋子。
## Output
请输出两个数字——玩家在一次移动中能获得的最大分数，以及能获得该最大分数的移动方式的数量。
[samples]
## Note
在第一个样例中，最大分数由位置为 #cf_span[(3, 3)] 的棋子获得。其移动过程如下图所示： 其他所有棋子获得的分数都更少。
**Definitions:**
- Let $ G = (V, E) $ be a directed graph where each vertex $ v \in V $ corresponds to a chip on an $ n \times m $ grid.
- Each chip at position $ (i, j) $ has a direction $ d \in \{ \text{L}, \text{R}, \text{U}, \text{D} \} $.
- For each chip $ v $ at $ (i, j) $ with direction $ d $, define its *target* as the closest chip in the direction $ d $ along row $ i $ (if $ d \in \{ \text{L}, \text{R} \} $) or column $ j $ (if $ d \in \{ \text{U}, \text{D} \} $). If no such chip exists, $ v $ has no outgoing edge.
- An edge $ v \to w $ exists iff $ w $ is the closest chip in the direction of $ v $'s arrow.
**Given:**
- Grid size $ n \times m $, with $ 1 \leq n, m, n \cdot m \leq 5000 $.
- Grid contains chips labeled by directions: 'L', 'R', 'U', 'D'; empty cells are '_'.
- At least one chip exists.
**Objective:**
1. For each chip $ v $, simulate the path $ v = v_0 \to v_1 \to \dots \to v_k $, where each $ v_{i+1} $ is the target of $ v_i $, until no target exists. The *score* of starting at $ v $ is $ k+1 $ (number of chips removed).
2. Let $ S = \max_{v \in V} \text{score}(v) $.
3. Let $ C = |\{ v \in V : \text{score}(v) = S \}| $.
**Output:**
$$
S, \quad C
$$
API Response (JSON)
{
"problem": {
"name": "C. Chip Play",
"description": {
"content": "Let's consider the following game. We have a rectangular field _n_ × _m_ in size. Some squares of the field contain chips. Each chip has an arrow painted on it. Thus, each chip on the field points in",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 4000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF89C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Let's consider the following game. We have a rectangular field _n_ × _m_ in size. Some squares of the field contain chips.\n\nEach chip has an arrow painted on it. Thus, each chip on the field points in...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "让我们考虑以下游戏。我们有一个大小为 #cf_span[n × m] 的矩形棋盘，某些格子上放置了棋子。\n\n每个棋子上都画有一个箭头，因此每个棋子指向以下四个方向之一：上、下、左或右。\n\n玩家可以选择一个棋子并进行一次移动。\n\n移动的流程如下：选定的棋子被标记为当前棋子。接着，玩家检查在当前棋子所在的行（或列）中，是否存在至少一个被当前棋子箭头所指向方向上的其他棋子。如果存在至少一个这样的棋子，则...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions:**\n\n- Let $ G = (V, E) $ be a directed graph where each vertex $ v \\in V $ corresponds to a chip on an $ n \\times m $ grid.\n- Each chip at position $ (i, j) $ has a direction $ d \\in \\{ ...",
"is_translate": false,
"language": "Formal"
}
]
}