Juego de la Serpiente de Miku (Editorial)

Idea

Necesitamos colocar una serpiente de longitud máxima en un campo de n \times m de modo que forme un ciclo (para que pueda moverse infinitamente). Además, dos celdas adyacentes de la serpiente no pueden apuntar una hacia la otra.

Como la serpiente debe formar un camino cerrado, nuestro objetivo es construir un ciclo que cubra la mayor cantidad posible de celdas.

Observación clave

Si al menos uno de los lados es par, podemos cubrir todo el campo (n \cdot m celdas). Si ambos lados son impares, el máximo es n \cdot m - 1.

Consideramos tres casos.

Caso 1: $m$ es par

Construimos un zigzag que pasa por cada celda exactamente una vez y se cierra en un ciclo:

• Columna izquierda (j = 0): la serpiente baja desde la fila $0$ hasta la fila n-1.

• Fila inferior (i = n-1): la serpiente va hacia la derecha desde la columna $0$ hasta la columna m-1.

• Última columna (j = m-1): la serpiente gira hacia arriba.

• Las columnas internas se alternan: las columnas impares van hacia arriba, las pares hacia abajo, conectadas por giros.

Longitud — n \cdot m.

Caso 2: $n$ es par, $m$ es impar

Construimos una solución para un campo de m \times n usando el Caso 1 (ya que $n$ es par y se convierte en el número de columnas), luego transponemos la cuadrícula, intercambiando las direcciones: U \leftrightarrow L, D \leftrightarrow R.

Longitud — n \cdot m.

Caso 3: tanto $n$ como $m$ son impares

Es imposible cubrir todo el campo con un ciclo (esto se puede demostrar con un argumento de paridad). Sin embargo, podemos cubrir n \cdot m - 1 celdas:

• Construimos un ciclo para el subcampo n \times (m-1) usando el Caso 1 (ya que m-1 es par).

• Extendemos el ciclo hacia la última columna: tomamos pares de filas y "estiramos" la serpiente hacia la derecha, añadiendo dos giros. Una celda queda sin cubrir.

Longitud — n \cdot m - 1.

¿Por qué se cumple la restricción de no retroceder?

El ciclo construido siempre tiene longitud $\ge 4$, por lo que cada celda apunta "hacia adelante" a lo largo del ciclo, y la situación en la que dos celdas adyacentes apuntan una hacia la otra nunca ocurre.

Complejidad

La construcción de la cuadrícula se realiza en un solo recorrido por todas las celdas.

En total: O(n \cdot m).

#include <bits/stdc++.h>
using namespace std;

vector<string> buildEvenCols(int n, int m) {
    vector<string> g(n, string(m, '.'));
    for (int i = 0; i < n - 1; i++) g[i][0] = 'D';
    g[n - 1][0] = 'R';
    for (int j = 1; j < m - 1; j++) g[n - 1][j] = 'R';
    g[n - 1][m - 1] = 'U';
    for (int j = 1; j < m; j++) {
        if (j % 2 == 1) {
            g[0][j] = 'L';
            for (int i = 1; i <= n - 2; i++) g[i][j] = 'U';
        } else {
            g[0][j] = 'D';
            for (int i = 1; i <= n - 3; i++) g[i][j] = 'D';
            g[n - 2][j] = 'L';
        }
    }
    return g;
}

vector<string> buildEvenRows(int n, int m) {
    vector<string> t = buildEvenCols(m, n);
    vector<string> g(n, string(m, '.'));
    auto swapDir = [](char c) -> char {
        switch (c) {
            case 'U': return 'L';
            case 'D': return 'R';
            case 'L': return 'U';
            case 'R': return 'D';
            default:  return c;
        }
    };
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            g[i][j] = swapDir(t[j][i]);
    return g;
}

vector<string> buildOddOdd(int n, int m) {
    vector<string> sub = buildEvenCols(n, m - 1);
    vector<string> g(n, string(m, '.'));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m - 1; j++)
            g[i][j] = sub[i][j];
    for (int i = 1; i <= n - 2; i += 2) {
        g[i + 1][m - 2] = 'R';
        g[i + 1][m - 1] = 'U';
        g[i    ][m - 1] = 'L';
    }
    return g;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;

    vector<string> g;
    int len;

    if (m % 2 == 0) {
        g = buildEvenCols(n, m);
        len = n * m;
    } else if (n % 2 == 0) {
        g = buildEvenRows(n, m);
        len = n * m;
    } else {
        g = buildOddOdd(n, m);
        len = n * m - 1;
    }

    cout << len << "\n";
    for (auto& row : g) cout << row << "\n";
    return 0;
}