Miku's Snake Game#12446

Miku's Snake Game (Editorial)

Problem author:	Andriy Kholod (Connect)
Prepared by:	Andriy Kholod (Connect)
Editorial:	Andriy Kholod (Connect)

Idea

We need to place a snake of maximum length on an $n \times m$ n \times m grid such that it forms a cycle (so it can move infinitely). Additionally, no two adjacent cells of the snake may point at each other.

Since the snake must form a closed path, our goal is to build a cycle that covers as many cells as possible.

Key observation

If at least one side is even, we can cover the entire grid ( $n \cdot m$ n \cdot m cells). If both sides are odd, the maximum is $n \cdot m - 1$ n \cdot m - 1.

We consider three cases.

Case 1: $m$ is even

We build a zigzag that visits every cell exactly once and closes into a cycle:

Left column ( $j = 0$ j = 0): the snake goes down from row $0$ to row $n - 1$ n-1.
Bottom row ( $i = n - 1$ i = n-1): the snake goes right from column $0$ to column $m - 1$ m-1.
Last column ( $j = m - 1$ j = m-1): the snake turns upward.
Inner columns alternate: odd columns go up, even columns go down, connected by turns.

Length — $n \cdot m$ n \cdot m.

Case 2: $n$ is even, $m$ is odd

We build a solution for an $m \times n$ m \times n grid using Case 1 (since $n$ is even and becomes the number of columns), then transpose the grid, swapping directions: $U \leftrightarrow L$ U \leftrightarrow L, $D \leftrightarrow R$ D \leftrightarrow R.

Length — $n \cdot m$ n \cdot m.

Case 3: both $n$ and $m$ are odd

It is impossible to cover the entire grid with a cycle (this can be shown by a parity argument). However, we can cover $n \cdot m - 1$ n \cdot m - 1 cells:

Build a cycle for the sub-grid $n \times (m - 1)$ n \times (m-1) using Case 1 (since $m - 1$ m-1 is even).
Extend the cycle into the last column: take pairs of rows and "pull" the snake to the right, adding two turns. One cell remains uncovered.

Length — $n \cdot m - 1$ n \cdot m - 1.

Why is the no-U-turn constraint satisfied?

The constructed cycle always has length $\geq 4$ , so every cell points "forward" along the cycle, and the situation where two adjacent cells point at each other never occurs.

Complexity

Building the grid is done in a single pass over all cells.

Overall: $O (n \cdot m)$ 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;
}

C++