P12625 [ICPC 2025 NAC] Mob Grinder

在某款流行的沙盒视频游戏中，玩家可以建造一种名为 *mob grinder*（怪物磨床）的结构。 一个 mob grinder 由 $N \times M$ 的矩形网格组成。怪物（或称 "mob"）会随机出现在网格各处。mob grinder 的目标是将所有怪物移动到网格右上角的格子，无论它们最初出现在哪里。为实现这一目标，每个格子（除右上角外）都装有一个指定方向（上、右、下、左）的传送带。怪物在传送带上会沿着传送带方向移动到相邻的格子。 你的任务是为每个格子（除右上角外）设置传送带方向，使得无论怪物出现在网格何处，都能在有限时间内被传送到右上角，且不会离开网格边界。但每种方向的传送带使用数量有限制：最终设计必须恰好使用 $U$ 个向上、$R$ 个向右、$D$ 个向下、$L$ 个向左的传送带。 你需要设计多个 mob grinder，每个都有特定的传送带使用数量要求。判断每个规格是否可行，若可行则输出有效设计。

第一行输入整数 $T$（$1 \leq T \leq 10^5$），表示需要设计的 mob grinder 数量。 接下来 $T$ 行每行包含六个整数，描述一个 mob grinder 规格：前两个整数 $N$ 和 $M$（$1 \leq N,M$ 且 $N \cdot M \leq 10^5$）表示网格的行列数；后四个整数 $U$、$R$、$D$、$L$（$0 \leq U, R, D, L$ 且 $U + R + D + L = (N \cdot M) - 1$）表示各方向传送带的使用数量。 保证所有 $T$ 个 mob grinder 的 $N \cdot M$ 总和不超过 $10^5$。

输出 $T$ 个 mob grinder 设计，每个规格对应一个，相邻设计用空行分隔。 若某规格无法构造有效设计，输出 $\texttt{impossible}$。否则输出 $N \times M$ 的 ASCII 字符网格：右上角格子为 $\texttt{*}$，其余格子为 $\texttt{U}$、$\texttt{R}$、$\texttt{D}$ 或 $\texttt{L}$，表示传送带方向。 **注意空白符敏感**：必须用恰好一个空行（仅含换行符）分隔设计，最后一行输出后不得有多余空行（但需以换行符结尾）。参见样例输出格式。

翻译由 DeepSeek V3 完成