CF2034C Trapped in the Witch's Labyrinth
题目描述
在《列王纪》传奇英雄鲁斯塔姆的第四个任务中，一个老女巫创造了一个迷宫来困住他。迷宫是一个 $n\times m$ 的矩形网格，迷宫中每一个单元格都有箭头，指向上、下、左或右的一个特定方向。女巫对鲁斯塔姆施了魔法，他每进入一个单元格，都会按照箭头的方向移动到下一个单元格。
如果鲁斯塔姆可以离开迷宫，他将战胜女巫。否则他将永远被困在迷宫中。
还有一些单元格的方向没有被女巫确定，她希望你指定一些方向，使得鲁斯塔姆能够被困住的起始格最多。你的任务是找到使得鲁斯塔姆被困住的最多起始单元格数。
输入格式
第一行，一个整数 $t$ ($1\le t\le 10^4$)，表示数据组数。
对于每组数据：
- 第一行，两个整数 $n,m$ ($1\le n,m\le 1000$)，表示迷宫的行数和列数。
- 接下来的 $n$ 行，每行 $m$ 个字符，表示这个迷宫。每个字符都是以下之一：
- `U`：向上；
- `D`：向下；
- `L`：向左；
- `R`：向右；
- `?`：未确定；
保证所有 $n\times m$ 之和不超过 $10^6$。
输出格式
对于每组数据，输出一个整数，表示使得鲁斯塔姆被困住的最多起始单元格数。
翻译：[HYdroKomide](https://www.luogu.com.cn/user/299883)
说明/提示
In the first test case, all of the cells will be good no matter what you do.
In the second test case, if you assign the ?s like the picture below, all of the cells will be bad:
In the third test case, if you assign the ?s like the picture below, you will have $ 5 $ bad cells (red-shaded cells):
