Miku-nun İlan Oyunu#12446

Miku-nun İlan Oyunu (Həll təhlili)

Məsələnin müəllifi:	Andriy Kholod (Connect)
Hazırlayan:	Andriy Kholod (Connect)
Həll analizi:	Andriy Kholod (Connect)

İdeya

$n \times m$ n \times m ölçülü sahədə maksimal uzunluqda ilan yerləşdirmək lazımdır ki, o dövr əmələ gətirsin (sonsuz hərəkət edə bilsin). Bundan əlavə, ilanın iki qonşu xanası bir-birinə işarə edə bilməz.

İlan qapalı yol əmələ gətirməli olduğundan, məqsədimiz mümkün qədər çox xananı əhatə edən dövr qurmaqdır.

Əsas müşahidə

Əgər tərəflərdən ən azı biri cütdürsə, bütün sahəni əhatə etmək mümkündür ( $n \cdot m$ n \cdot m xana). Əgər hər iki tərəf təkdirsə, maksimum $n \cdot m - 1$ n \cdot m - 1-dir.

Üç halı nəzərdən keçirək.

Hal 1: $m$ cütdür

Hər xanadan tam bir dəfə keçən və dövrə bağlanan ziqzaq qururuq:

Sol sütun ( $j = 0$ j = 0): ilan $0$ -cı sətirdən $n - 1$ n-1-ci sətirə qədər aşağı gedir.
Alt sətir ( $i = n - 1$ i = n-1): ilan $0$ -cı sütundan $m - 1$ m-1-ci sütuna qədər sağa gedir.
Son sütun ( $j = m - 1$ j = m-1): ilan yuxarı dönür.
Daxili sütunlar növbələşir: tək sütunlar yuxarı, cüt sütunlar aşağı gedir, dönüşlərlə birləşir.

Uzunluq — $n \cdot m$ n \cdot m.

Hal 2: $n$ cütdür, $m$ təkdir

$m \times n$ m \times n sahəsi üçün Hal 1-dən istifadə edərək həll qururuq ( $n$ cüt olduğundan sütun sayına çevrilir), sonra şəbəkəni transponə edirik, istiqamətləri dəyişdiririk: $U \leftrightarrow L$ U \leftrightarrow L, $D \leftrightarrow R$ D \leftrightarrow R.

Uzunluq — $n \cdot m$ n \cdot m.

Hal 3: həm $n$ , həm $m$ təkdir

Bütün sahəni dövrə ilə əhatə etmək mümkün deyil (bunu paritet arqumenti ilə göstərmək olar). Lakin $n \cdot m - 1$ n \cdot m - 1 xananı əhatə etmək mümkündür:

$n \times (m - 1)$ n \times (m-1) alt-sahəsi üçün Hal 1-dən istifadə edərək dövr qururuq ( $m - 1$ m-1 cüt olduğundan).
Dövrü son sütuna genişləndiririk: sətir cütlərini götürüb ilanı sağa "dartırıq", iki dönüş əlavə edirik. Bir xana əhatə olunmamış qalır.

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

Geri dönüş qadağası niyə ödənilir?

Qurulmuş dövr həmişə $\geq 4$ uzunluğa malikdir, buna görə hər xana dövr boyunca "irəli" işarə edir və iki qonşu xananın bir-birinə işarə etməsi vəziyyəti yaranmır.

Asimptotika

Şəbəkənin qurulması bütün xanalar üzərində bir keçidlə həyata keçirilir.

Beləliklə: $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++