← 返回题目列表

Codeforces · 2034/C

C. 被困在女巫的迷宫中

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

在《列王纪》中的传奇英雄罗斯坦的第四次劳动中,一位老女巫创造了一个魔法迷宫来困住他。迷宫是一个矩形网格,由 $$$n$$$ 行和 $$$m$$$ 列组成。迷宫中的每个单元格都指向特定的方向:上、下、左或右。女巫对罗斯坦施了魔法,只要他在一个牢房里,他就会按照该牢房指示的方向移动到下一个牢房。

如果罗斯坦最终退出迷宫,他将摆脱女巫的魔咒并击败她。然而,如果他永远被困在迷宫里,他就永远无法逃脱。

女巫尚未确定所有细胞的方向。她希望为未指定的单元格分配方向,以使罗斯坦永远被困的起始单元格数量最大化。你的任务是找到使罗斯塔姆被困的起始单元格的最大数量。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$),即测试用例的数量。

对于每个测试用例:

- 第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 1000$$$),代表迷宫中的行数和列数。
- 接下来的 $$$n$$$ 行包含一串 $$$m$$$ 字符,表示迷宫中的方向。每个字符都是以下字符之一: U(上) D(下) L(左) R(右) ? (未指定方向)

保证所有测试用例的 $$$n \cdot m$$$ 之和最多为 $$$10^6$$$。

输出

对于每个测试用例,打印一个整数,即在为未指定单元格最佳分配方向后,Rostam 将永远被捕获的起始单元格的最大数量。

示例

输入 #1

3
3 3
UUU
L?R
DDD
2 3
???
???
3 3
?U?
R?L
RDL

输出 #1

0
6
5

注意

在第一个测试用例中,无论您做什么,所有单元格都会正常。

在第二个测试用例中,如果您如下图所示分配 ?,则所有单元格都将是坏的:

在第三个测试用例中,如果您像下图一样分配 ?,您将有 $$$5$$$ 坏单元格(红色阴影单元格):