#P9767. [2020年省队模拟]机器人的躲猫猫

    ID: 6396 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-二分图建模顶点覆盖坐标变换线性 DP前后缀最值滚动数组路径恢复网格 DP

[2020年省队模拟]机器人的躲猫猫

题目描述

D 神在一个 mm 行、nn 列的网格上进行机器人躲猫猫游戏。一些格子中站着机器人,其余格子为空。每个机器人面向上、下、左或右之一,分别用 U、D、L、R 表示。

以向下看的机器人为例。在它正下方第 dd 行(d≥1d\ge 1),所有列差绝对值不超过 d−1d-1 的格子均在视野内。向上时同理。向左或向右时,在朝向一侧第 dd 列,所有行差绝对值不超过 d−1d-1 的格子均在视野内。只计算网格内的格子。其他机器人不会遮挡视野。

向下的机器人及其视野

你可以让每个机器人保持不动,或顺时针、逆时针转 90∘90^\circ。在最终网格中,不能有两个机器人彼此都能看见对方。只看见对方而未被对方看见是允许的。求转向的机器人数量最少的一种方案。保证至少有一种合法方案。

输入格式

第一行包含两个整数 m,nm,n,分别表示网格的行数和列数。1≤m,n≤20001\le m,n\le 2000。

接下来 mm 行,每行 nn 个字符,描述网格。其中 U、D、L、R 表示机器人的方向,. 表示空格子。

输出格式

输出 mm 行,每行 nn 个字符,描述转向后的网格。机器人原来的位置和所有空格子都不变。如果有多种最优方案,输出任意一种。

样例输入

2 3
RDL
.U.

样例输出

UDL
.R.
限制 分值
1 1≤n,m≤101\leq n,m \leq 10 10
2 nn 或者 mm 其中之一 ≤10\leq 10 30
3 1≤n,m≤20001 \leq n, m \leq 2000 60