Juego de la Serpiente de Miku#12446
Miku está jugando al clásico juego Snake.
El juego se juega en un tablero rectangular con filas y columnas. La serpiente consiste en varias celdas consecutivas del tablero. En cada paso, la cabeza de la serpiente se mueve a una de las cuatro celdas vecinas: arriba, abajo, izquierda o derecha. Después de eso, cada otro segmento de la serpiente sigue al segmento que estaba directamente delante de él.
La serpiente no puede salir del tablero, y ningún par de segmentos de su cuerpo puede ocupar la misma celda.
Miku quiere colocar una serpiente de la máxima longitud posible en el tablero de modo que, después de empezar a moverse, pueda moverse para siempre.
Debes imprimir cualquier colocación de este tipo.
La colocación debe describirse como una tabla con filas y columnas. Cada celda debe contener uno de cinco símbolos:
"L" — esta celda pertenece a la serpiente, y el siguiente segmento de la serpiente está ubicado en la celda vecina de la izquierda;
"R" — esta celda pertenece a la serpiente, y el siguiente segmento de la serpiente está ubicado en la celda vecina de la derecha;
"U" — esta celda pertenece a la serpiente, y el siguiente segmento de la serpiente está ubicado en la celda vecina de arriba;
"D" — esta celda pertenece a la serpiente, y el siguiente segmento de la serpiente está ubicado en la celda vecina de abajo;
"." — esta celda no pertenece a la serpiente.
En otras palabras, si empiezas desde cualquier celda de la serpiente y te mueves repetidamente según el símbolo escrito en la celda actual, debes visitar todas las celdas de la serpiente y volver a la celda de inicio. Gracias a esto, la serpiente podrá moverse para siempre.
Además, la serpiente no puede regresar inmediatamente a la celda de la que acaba de venir. Formalmente, no debe existir un par de celdas vecinas de la serpiente y tal que el símbolo en la celda apunte a la celda , y el símbolo en la celda apunte de vuelta a la celda .
Por ejemplo, una celda con símbolo "D" ubicada directamente encima de una celda con símbolo "U" está prohibida. Del mismo modo, una celda con símbolo "R" ubicada directamente a la izquierda de una celda con símbolo "L" está prohibida.
Si hay varias colocaciones correctas de longitud máxima, imprime cualquiera de ellas.
La única línea contiene dos enteros y (2 \le n, m \le 1000) — las dimensiones del tablero.
En la primera línea, imprime un entero — la longitud máxima de una serpiente que puede colocarse en el tablero de modo que pueda moverse para siempre.
En las siguientes líneas, imprime caracteres en cada una — la descripción de la colocación de la serpiente.
El número de celdas no vacías, es decir, celdas con símbolos "L", "R", "U" o "D", debe ser igual a .
Ejemplo 1
Ejemplo 2
En el primer ejemplo, el tablero tiene tamaño 3 \times 5. Como ambas dimensiones son impares, la serpiente no puede ocupar todas las celdas. Una colocación óptima tiene longitud .
Si empiezas desde la celda y sigues las flechas, la serpiente visitará las celdas ocupadas y volverá a la celda , así que puede moverse para siempre.
En el segundo ejemplo, el tablero tiene tamaño 4 \times 4. En este caso, la serpiente puede ocupar las celdas.
Subtarea ( puntos): y son pares.
Subtarea ( puntos): al menos uno de y es par.
Subtarea ( puntos): Sin restricciones adicionales.