CF1335F Robots on a Grid

有一个大小为 $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'。 你想在这个场地上放置一些机器人（每个格子最多只能放一个机器人）。需要满足以下条件： - 首先，每个机器人每次都必须移动（即不能跳过移动）。每次移动时，机器人会根据当前格子的方向移动到相邻的格子。 - 其次，你需要放置机器人，使得在任意一次移动之前，任意两个不同的机器人都不会占据同一个格子（这也意味着不能在同一个格子放两个机器人）。例如，如果网格为 "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)$ 为黑色则为 '0'，为白色则为 '1'）。 再接下来的 $n$ 行，每行包含 $m$ 个字符，第 $i$ 行第 $j$ 个字符为 $s_{i, j}$（'U'、'R'、'D' 或 'L'，表示格子 $(i, j)$ 的方向）。 保证所有测试用例的网格总大小不超过 $10^6$（$\sum nm \le 10^6$）。

对于每组测试用例，输出两个整数，分别表示在满足所有条件的情况下最多能放置多少个机器人，以及在机器人数量最大时，初始占据的黑色格子的最大数量。注意，机器人只能在所有移动开始之前放置。

由 ChatGPT 4.1 翻译