4416. [ICPC2026河南省赛]贪玩迷宫

【题目描述】

小 C 正被困在一个 $n$ 行 $m$ 列的二维迷宫里，这个迷宫有若干个终点（用大写字母 O 表示），到达这些终点位置就可以逃出迷宫。在非终点的位置有一个导向标，写着 UDLR 四个字母中的一种，在这些位置上，必须按 UDLR 的指示向上、下、左、右移动。

小 C 可以任选一个非终点位置出发，可能被困死在循环里，可能成功到达终点中的一个，还有可能撞上边界。小 C 有一次作弊操作，可以选择在出发前修改一个非终点位置的导向标。同时小 C 也比较贪玩，他想在保证能到达终点的前提下尽可能多地在迷宫里移动。

如果不使用作弊操作，可能每个非终点位置都无法到达终点。但是通过使用作弊操作可以保证存在至少一个能到达终点的非终点位置。请问至多使用一次作弊操作后，保证能到达终点的前提下他最多可以移动几次？

【输入格式】

第一行一个正整数 $T$（$1 \le T \le 10$）表示一共有 $T$ 个测试用例。每个测试用例占 $n+1$ 行，第一行两个整数 $n,m$（$2 \le n,m \le 1000, \sum n∗m \le 10^6$）表示二维迷宫的行和列。

接下来 $n$ 行，每行一个长为 $m$ 的字符串，表示二维迷宫的每一行。保证字符串里只包含 O, U, D, L, R，分别表示终点，向上，向下，向左，向右，至少存在一个终点位置，至少存在一个非终点位置。

【输出格式】

对于每个测试用例输出一行一个整数，代表答案。

【输入样例】

3
3 3
DLL
DOU
RRU
3 7
RDLLLLL
UDRRROU
URRRRRU
3 3
ODL
ROL
RRU

【输出样例】

8
20
6

【样例说明】

对于第一个地图，如果不做修改，小 C 从任意一个非终点位置出发都会被困死在循环里。如果小 C 将第一行第二列位置的 L 修改为 D，再从第一行第一列位置出发就可以移动 $8$ 次。还有其他的可行修改，能到达终点的前提下，能移动的次数一定小于等于 $8$。

对于第二个地图，将第一行第三列的 L 修改为 D，再从第三行第一列位置出发可以移动 $20$ 次。

对于第三个地图，将第二行第三列的 L 修改为 U，再从第三行第一列位置出发可以移动 $6$ 次。

【来源】

ICPC 2026 河南省赛。