Задача №114870. Робо-прятки
Миша занимается конструированием роботов для игры в робо-прятки. Игра в робо-прятки происходит на клетчатом поле \(m \times n\), в некоторых клетках которого расположены роботы.
Каждый робот изначально смотрит в одном из четырех направлений: вверх, вниз, влево или вправо. У каждого робота есть его поле зрения. Рассмотрим робота, смотрящего вниз. В его поле зрения находится одна клетка, расположенная в следующей строке, три клетки, расположенные в строке через одну, пять — в строке через две, и так далее. В \(k\)-й из следующих строк в поле зрения робота находятся \(2k - 1\) клеток, образующих отрезок, центром которого является клетка, расположенная в том же столбце, что и робот.
Области зрения роботов, смотрящих вправо, вверх и влево определяются аналогично.
Робот \(A\) видит робота \(B\), если клетка, в которой расположен робот \(B\), находится в поле зрения робота \(A\). Для того, чтобы начать игру в робо-прятки, необходимо сделать так, чтобы на поле не существовало пары роботов, которые видят друг друга. Иначе говоря, для любой пары роботов \(A\), \(B\) должно выполняться хотя бы одно из двух условий: \(A\) не видит \(B\) или \(B\) не видит \(A\).
Миша может за одну операцию повернуть любого робота на 90 градусов по или против часовой стрелки, поменяв соответствующим образом направление, в котором смотрит робот. Он хочет начать игру как можно скорее, поэтому хочет сделать минимальное количество операций, чтобы получить конфигурацию, при которой можно начать игру.
Помогите ему найти такую конфигурацию. Можно доказать, что для любого начального расположения роботов искомая конфигурация существует.
В первой строке ввода находятся два целых числа \(m\) и \(n\) — количество строк и столбцов на поле (\(1 \le n, m \le 2\,000\)).
Следующие \(m\) строк состоят каждая из \(n\) символов « U », « D », « L », « R » или « . ». Символ « U » означает, что в клетке находится робот, смотрящий вверх, символ « D » — вниз, « L » — влево, « R » — вправо, а « . » — что в клетке нет робота.
Выведите \(m\) строк по \(n\) символов в каждой — конфигурацию, в которой можно начать игру. Конфигурация должна получаться из заданной во входных данных за минимальное число операций поворота робота на 90 градусов. Если оптимальных ответов несколько, вы можете вывести любой.
Обратите внимание, что Миша может только поворачивать роботов, но не может перемещать, удалять или добавлять их. Следовательно в выведенном ответе роботы должны находится в тех и только тех клетках, в которых они находились во входных данных.
2 3 RDL .U.
RDD .R.
2 2 .. ..
.. ..