← 返回题目列表

Codeforces · 1335/F

F. 网格上的机器人

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

有一个大小为 $$$n \times m$$$ 的矩形网格。网格的每个单元格颜色为黑色(“0”)或白色(“1”)。单元格$$$(i, j)$$$的颜色是$$$c_{i, j}$$$。您还会获得一张方向图:对于每个单元格,都有一个方向 $$$s_{i, j}$$$,它是四个字符“U”、“R”、“D”和“L”之一。

- 如果 $$$s_{i, j}$$$ 为 'U',则存在从单元格 $$$(i, j)$$$ 到单元格 $$$(i - 1, j)$$$ 的转换;
- 如果 $$$s_{i, j}$$$ 是 'R' 则存在从单元格 $$$(i, j)$$$ 到单元格 $$$(i, j + 1)$$$ 的转换;
- 如果 $$$s_{i, j}$$$ 为 'D',则存在从单元格 $$$(i, j)$$$ 到单元格 $$$(i + 1, j)$$$ 的转换;
- 如果 $$$s_{i, j}$$$ 为“L”,则存在从单元格 $$$(i, j)$$$ 到单元格 $$$(i, j - 1)$$$ 的转换。

保证顶行不包含字符“U”,底行不包含字符“D”,最左列不包含字符“L”,最右列不包含字符“R”。

您想在此字段中放置一些机器人(一个单元中最多有一个机器人)。应满足以下条件。

- 首先,每个机器人每次都应该移动(即它不能跳过移动)。在一次移动过程中,每个机器人根据当前方向前往相邻单元。
- 其次,你必须以这样的方式放置机器人,即在两个不同的机器人占据同一个单元之前没有任何移动(这也意味着你不能将两个机器人放置在同一个单元中)。 IE。如果网格是“RL”(一行,两列,颜色在那里并不重要),那么您可以将两个机器人放置在单元格 $$$(1, 1)$$$ 和 $$$(1, 2)$$$ 中,但是如果网格是“RLL”,那么您不能将机器人放置在单元格 $$$(1, 1)$$$ 和 $$$(1, 3)$$$ 中,因为在第一秒内两个机器人都会占据单元格 $$$(1, 2)$$$。

机器人进行无限次移动。

你的任务是放置最多数量的机器人以满足上述所有条件,并且在所有这些方式中,你必须选择一种在所有移动之前机器人占据的黑色单元格数量最多的方式。请注意,您只能将机器人放置在所有动作之前。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 < nm \le 10^6$$$) — 相应的行数和列数。

接下来的 $$$n$$$ 行每行包含 $$$m$$$ 个字符,其中第 $$$i$$$ 行的第 $$$j$$$ 个字符是 $$$c_{i, j}$$$ (如果单元格 $$$(i, j)$$$ 为黑色,则 $$$c_{i, j}$$$ 为“0”;如果单元格 $$$(i, j)$$$ 为黑色,则为“1” $$$(i, j)$$$ 是白色)。

接下来的 $$$n$$$ 行每行也包含 $$$m$$$ 个字符,其中第 $$$i$$$ 行的第 $$$j$$$ 个字符是 $$$s_{i, j}$$$ ($$$s_{i, j}$$$ 是 'U'、'R'、'D' 或 'L',并描述单元格的方向$$$(i,j)$$$)。

保证字段大小的总和不超过$$$10^6$$$ ($$$\sum nm \le 10^6$$$)。

输出

对于每个测试用例,打印两个整数——满足问题陈述中描述的所有条件可以放置的机器人的最大数量,以及如果放置的机器人数量最大化,则在所有移动之前机器人占据的黑色单元的最大数量。请注意,您只能将机器人放置在所有动作之前。

示例

输入 #1

3
1 2
01
RL
3 3
001
101
110
RLL
DLD
ULL
3 3
000
000
000
RRD
RLD
ULL

输出 #1

2 1
4 3
2 2