Гра Змійка Міку#12446

Гра Змійка Міку (Розбір)

Автор задачі:	Андрій Холод (Connect)
Підготував:	Андрій Холод (Connect)
Розбір:	Андрій Холод (Connect)

Ідея

Потрібно розмістити на полі $n \times m$ n \times m змійку максимальної довжини, яка утворює цикл (щоб рухатись нескінченно). При цьому дві сусідні клітинки змійки не можуть вказувати одна на одну.

Змійка має утворювати замкнений шлях, тому наша мета — побудувати цикл, що покриває якомога більше клітинок.

Ключове спостереження

Якщо хоча б одна зі сторін парна, можна покрити все поле ( $n \cdot m$ n \cdot m клітинок). Якщо обидві сторони непарні, максимум — $n \cdot m - 1$ n \cdot m - 1.

Розглянемо три випадки.

Випадок 1: $m$ парне

Будуємо зиґзаґ, що проходить через кожну клітинку рівно один раз і замикається в цикл:

Лівий стовпець ( $j = 0$ j = 0): змійка йде вниз від рядка $0$ до рядка $n - 1$ n-1.
Нижній рядок ( $i = n - 1$ i = n-1): змійка йде вправо від стовпця $0$ до стовпця $m - 1$ m-1.
Останній стовпець ( $j = m - 1$ j = m-1): змійка повертає вгору.
Внутрішні стовпці чергуються: непарні стовпці йдуть вгору, парні — вниз, з'єднуючись поворотами.

Довжина — $n \cdot m$ n \cdot m.

Випадок 2: $n$ парне, $m$ непарне

Будуємо розв'язок для поля $m \times n$ m \times n за Випадком 1 (бо $n$ парне, і воно стає кількістю стовпців), а потім транспонуємо сітку, замінюючи напрямки: $U \leftrightarrow L$ U \leftrightarrow L, $D \leftrightarrow R$ D \leftrightarrow R.

Довжина — $n \cdot m$ n \cdot m.

Випадок 3: $n$ і $m$ обидва непарні

Покрити все поле циклом не вдасться (можна показати паритетним аргументом). Проте можна покрити $n \cdot m - 1$ n \cdot m - 1 клітинок:

Будуємо цикл для підполя $n \times (m - 1)$ n \times (m-1) за Випадком 1 (бо $m - 1$ m-1 парне).
Розширюємо цикл в останній стовпець: беремо пари рядків і "витягуємо" змійку вправо, додаючи два повороти. Одна клітинка залишається непокритою.

Довжина — $n \cdot m - 1$ n \cdot m - 1.

Чому заборона розвороту виконується?

Побудований цикл завжди має довжину $\geq 4$ , тому кожна клітинка вказує "вперед" по циклу, і ситуація, коли дві сусідні клітинки вказують одна на одну, не виникає.

Асимптотика

Побудова сітки виконується за один прохід по всіх клітинках.

Отже маємо $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++