logoChat01.ai

правильно ли код решает задачу: #include <bits/std...

Creato il: 17 agosto 2026

Risposto usando GPT-5.5 da Chat01

Domanda

правильно ли код решает задачу:
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define all(x) x.begin(), x.end()
#define forn(x, y) for (int i = x; i < y; i++)
using ld = long double;
using ll = long long;

const int max_n = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e9 + 5;
vector<int> logs;

int x, y;
int a, b;
int flag;

bool move(char t) {
cout << t << "\n";
cout.flush();
if (t == 'R') y++;
if (t == 'L') y--;
if (t == 'U') x--;
if (t == 'D') x++;
string res; cin >> res;
if (res == "win" || res == "fail") {
exit(0);
}
if (res == "new") {
cin >> a >> b;
return true;
}
return false;
}

void solve() {
int n, m; cin >> n >> m;
cin >> x >> y;
cin >> a >> b;
if (n % 2 == 0) {
if (a == 1 && b == 1) {
while (y < m) move('R');
while (x < n) move('D');
while (y > 1) move('L');
while (x > 1) move('U');
} else {
while (y < m) {
if (a == x && b == y + 1) break;
move('R');
}
while (x < n) {
if (a == x + 1 && b == y) break;
move('D');
}
while (y > 1) {
if (a == x && b == y - 1) move('U');
move('L');
}
while (x > 1) {
if (a == x - 1 && b == y) {
move('R');
move('U');
move('U');
move('L');
}
if (x != 1) move('U');
}
}
while (true) {
while (x < n) {
while (y < m) move('R');
move('D');
while (y > 2) move('L');
if (x != n) move('D');
}
move('L');
while (x > 1) move('U');
}
}
if (m % 2 == 0) {
if (a == 1 && b == 1) {
while (x < n) move('D');
while (y < m) move('R');
while (x > 1) move('U');
while (y > 1) move('L');
} else {
while (x < n) {
if (a == x + 1 && b == y) break;
move('D');
}
while (y < m) {
if (a == x && b == y + 1) break;
move('R');
}
while (x > 1) {
if (a == x - 1 && b == y) {
move('L');
}
move('U');
}
while (y > 1) {
if (a == x && b == y - 1) {
move('D');
move('L');
move('L');
move('U');
}
if (y > 1) move('L');
}
}
while (true) {
while (y < m) {
while (x < n) move('D');
move('R');
while (x > 2) move('U');
if (y != m) move('R');
}
move('U');
while (y > 1) move('L');
}
}
if (a == 1 && b == 1) {
while (x < n) move('D');
while (y < m) move('R');
while (x > 1) move('U');
while (y > 1) move('L');
} else {
while (x < n) {
if (a == x + 1 && b == y) break;
move('D');
}
while (y < m) {
if (a == x && b == y + 1) break;
move('R');
}
while (x > 1) {
if (a == x - 1 && b == y) {
move('L');
}
move('U');
}
while (y > 1) {
if (a == x && b == y - 1) {
move('D');
move('L');
move('L');
move('U');
}
if (y > 1) move('L');
}
}
while (true) {
if (b == m) flag = 1;
else flag = 0;
if (flag) {
while (x < n) move('D');
move('R');
move('R');
while (x > 2) move('U');
if (y != m) move('R');
while (y < m) {
while (x < n) move('D');
move('R');
while (x > 2) move('U');
if (y != m) move('R');
}
move('U');
while (y > 1) move('L');
} else {
while (y < m - 1) {
while (x < n) move('D');
move('R');
while (x > 2) move('U');
if (y != m - 1) move('R');
}
move('U');
while (y > 1) move('L');
}
}
}

signed main() {
/*ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif*/

text
int t = 1;
//cin >> t;

logs.resize(max_n, 0);
for (int i = 2; i < max_n; i++) logs[i] = logs[i / 2] + 1;

while (t--) {
    solve();
    cout << "\n";
}

}

Легендарный Шаи-Хулуд, как вы можете себе представить, не всегда был самым большим и
могущественным червем в Берляндии. Когда-то он был обыкновенным червячком. Вырос он, поедая
радиоактивные яблоки.
Злой дух уменьшил Шаи-Хулуда за его проделки, и теперь Шаи-Хулуд ищет новые яблоки,
чтобы вырасти до старых размеров.
Шаи-Хулуд живет на клетчатом поле размерами n × m. Изначально он занимает одну клетку
этого поля. Он может перемещаться на одну клетку горизонтально или вертикально, не выходя за
границы поля.
На поле находится яблоко. Когда Шаи-Хулуд съедает яблоко, его размер увеличивается на 1. А
именно, его тело увеличивается в длине, голова начинает занимать клетку с яблоком, а все остальные
клетки тела Шаи-Хулуда не двигаются. Это поведение может быть знакомо по классической игре
"Змейка".
Более формально, тело Шаи-Хулуда представляет собой последовательность клеток от головы
к хвосту. Каждые две соседние клетки в этой последовательности являются соседними по стороне
на поле, и никакая клетка не встречается в последовательности дважды.
Пусть Шаи-Хулуд перемещает голову в соседнюю клетку q.
Если в клетке q находится яблоко, клетка q добавляется в начало последовательности, а остальные клетки тела остаются на месте.
Если яблока в клетке q нет, сначала из последовательности удаляется последняя клетка — хвост
Шаи-Хулуда, после чего клетка q добавляется в начало последовательности.
После выполнения хода все клетки тела должны быть различны, а голова не должна находиться
за пределами поля. В частности, при ходе без поедания яблока разрешается переместить голову в
клетку, в которой непосредственно перед ходом находился хвост.
После поедания яблока в одной из свободных клеток появляется новое яблоко. Ваша цель —
вырастить Шаи-Хулуда так, чтобы он занял всё поле.
Протокол взаимодействия
В первой строке тестирующая программа выведет два целых числа n и m — размеры поля
(2 ⩽ n, m ⩽ 10).
Во второй строке будут находиться два целых числа xs и ys — координаты начальной позиции
Шаи-Хулуда (1 ⩽ xs ⩽ n, 1 ⩽ ys ⩽ m).
В третьей строке будут находиться два целых числа xa и ya — координаты первого яблока
(1 ⩽ xa ⩽ n, 1 ⩽ ya ⩽ m).
Для совершения хода выведите один из следующих символов:
• U — вверх;
• D — вниз;
• L — влево;
• R — вправо.
В ответ тестирующая программа выведет одно из следующих слов:
• ok — ход выполнен, яблоко не было съедено;
• new — яблоко было съедено. В следующей строке будут выведены два целых числа xa и ya —
координаты нового яблока;
Страница 1 из 3
• win — Шаи-Хулуд занял всё поле. Завершите программу, ничего больше не выводя;
• fail — был сделан запрещённый ход или превышено допустимое количество ходов. Немедленно
завершите программу.
Гарантируется, что каждое новое яблоко появляется в свободной клетке поля.
Разрешается сделать не более 100, 000 ходов.

Python

python
import random, collections

class Fail(Exception):
    pass
class Win(Exception):
    pass

def run(n,m,start,apple, chooser, maxmoves=100000):
    x,y=start
    a,b=apple
    body=collections.deque([(x,y)]) # head first
    moves=0
    
    def mv(t):
        nonlocal x,y,a,b,moves,body
        dxdy={'R':(0,1),'L':(0,-1),'U':(-1,0),'D':(1,0)}
        dx,dy=dxdy[t]
        nx,ny=x+dx,y+dy
        moves+=1
        if moves>maxmoves: raise Fail(("limit",moves,list(body),(a,b),t))
        if not (1<=nx<=n and 1<=ny<=m):
            raise Fail(("boundary",moves,(x,y),t,(a,b),list(body)))
        eat=(nx,ny)==(a,b)
        if eat:
            # cannot move into any occupied body cell because no tail removed
            if (nx,ny) in body:
                raise Fail(("collision eat",moves,(nx,ny),list(body)))
            body.appendleft((nx,ny))
            x,y=nx,ny
            if len(body)==n*m: raise Win(moves)
            free=[(i,j) for i in range(1

(4,
 7,
 9,
 (5, 4),
 (1, 3),
 ('collision',
  1107,
  (7, 3),
  [(7, 2),
   (7, 1),
   (6, 1),
   (5, 1),
   (4, 1),
   (3, 1),
   (2, 1),
   (1, 1),
   (1, 2),
   (1, 3),
   (1, 4),
   (1, 5),
   (1, 6),
   (1, 7),
   (1, 8),
   (2, 8),
   (3, 8),
   (4, 8),
   (5, 8),
   (6, 8),
   (7, 8),
   (7, 7),
   (6, 7),
   (5, 7),
   (4, 7),
   (3, 7),
   (2, 7),
   (2, 6),
   (3, 6),
   (4, 6),
   (5, 6),
   (6, 6),
   (7, 6),
   (7, 5),
   (6, 5),
   (5, 5),
   (4, 5),
   (3, 5),
   (2, 5),
   (2, 4),
   (3, 4),
   (4, 4),
   (5, 4),
   (6, 4),
   (7, 4),
   (7, 3),
   (6, 3),
   (5, 3),
   (4, 3)],
  (3, 3),
  (4, 9),
  'R'))

Pensiero

Found minimal counterexamples for snake cycles and apple sequences

Worked for 1m 7s

Risposta

Нет, код не гарантирует решение. В случае, когда и n, и m нечётные, можно получить запрещённый ход из-за столкновения головы с телом.

Я промоделировал твой алгоритм вместе с правилами интерактора. Уже на поле 3 × 3 находится контрпример.

Например:

text
n = 3, m = 3
старт = (3, 3)
первое яблоко = (2, 2)

После съедания яблок интерактор может легально выдавать следующие позиции:

text
(2,2)   <- первое
(3,3)
(2,1)
(3,2)
(1,3)
(1,2)
(2,2)
(3,3)

Все эти яблоки в момент появления находятся в свободных клетках, то есть такой тест полностью допустим.

После 37 ходов непосредственно перед ошибочным ходом тело змеи, от головы к хвосту, имеет вид:

text
(2,2) <- голова
(3,2)
(3,1)
(2,1)
(1,1)
(1,2)
(1,3)

хвост находится в (1,3), а яблоко — в (3,3).

Твой алгоритм затем делает:

cpp
move('U');

то есть пытается перейти

text
(2,2) -> (1,2)

Но (1,2) всё ещё занята телом змеи. Перед ходом без яблока удаляется только хвост (1,3), поэтому (1,2) не освобождается. Интерактор отвечает fail.

Главная проблема именно в нечётном случае:

cpp
while (true) {
    if (b == m) flag = 1;
    else flag = 0;

    if (flag) {
        ...
    } else {
        ...
    }
}

Ты фактически используешь два разных циклических маршрута и переключаешься между ними в зависимости от того, находится ли яблоко в последнем столбце.

Пока змейка короткая, это работает. Но после нескольких переключений тело расположено согласно предыдущему маршруту. Новый маршрут может пройти по клетке, которая ещё находится внутри тела. То есть условие

cpp
b == m

ничего не говорит о том, безопасно ли сейчас переключаться на другой цикл.

Для случая, когда n или m чётно, ситуация гораздо лучше: там основная часть действительно представляет собой гамильтонов цикл, например при чётном n:

text
→→→...
↓
←←...
↓
→→...
...
↑ по первому столбцу

Если змейка всё время движется в одном направлении по фиксированному гамильтонову циклу, столкнуться с собой она не может: голова движется за хвостом по тому же циклическому порядку.

Но для odd × odd гамильтонова цикла всего поля вообще быть не может: клетчатый граф двудольный, а количество вершин n*m нечётно. Поэтому здесь и требуется отдельная аккуратная конструкция; простое переключение между двумя циклами недостаточно.

Ещё несколько небольших моментов в коде сами по себе не являются основной ошибкой:

cpp
bool move(char t)

возвращаемое значение нигде не используется;

cpp
vector<int> logs;

и вычисление логарифмов вообще не нужны;

cpp
#define forn(x, y) for (int i = x; i < y; i++)

тоже не используется.

Но они на корректность интерактива не влияют.

Итог: решение получит fail на допустимых тестах. Критический случай — n % 2 == 1 && m % 2 == 1.

Если хочешь, я могу дальше разобрать именно нечётный случай и показать, как исправить твою идею с двумя циклами, не переписывая всё решение с нуля.

Domanda

разбери нечетный случай

Risposta

Да. В нечётном случае у тебя основная проблема не в конкретной команде, а в самой структуре маршрута.

Когда n и m нечётные, число клеток n*m тоже нечётно. Обычного гамильтонова цикла по всем клеткам не существует: поле — двудольный граф, а любой цикл в двудольном графе имеет чётную длину. Поэтому нельзя сделать то же самое, что в случаях с чётным n или m: выбрать один замкнутый маршрут через все клетки и бесконечно по нему ходить.

У тебя идея такая:

cpp
if (b == m) flag = 1;
else flag = 0;

То есть если яблоко в последнем столбце, используем один маршрут, иначе другой. Схематично это попытка временно исключить одну клетку/полосу, чтобы получить чётное число клеток и двигаться по циклу.

Сама идея разумная. Ошибка в том, что ты переключаешь маршрут, ориентируясь только на позицию яблока, но не на конфигурацию тела.

Представим 5 × 5. Можно построить цикл по 24 клеткам, исключив, например, (1,5):

text
1  → → → ↓
↑  ← ← ← ↓
↑  → → → ↓
↑  ← ← ← ↓
↑  → → → ↓

условно. Пока змейка движется строго по одному такому циклу, всё безопасно.

Можно построить другой цикл по 24 клеткам, исключив другую клетку, например (1,4). Он тоже отдельно безопасен.

Но из этого не следует, что можно безопасно сделать:

text
цикл A → несколько ходов → цикл B

Пусть по циклу A порядок клеток такой:

text
... → X → A → B → C → D → ...

И тело сейчас:

text
голова = X
A
B
C
D = хвост

Следующий ход по циклу A безопасен, потому что идёт в клетку, которая либо свободна, либо как раз является старым хвостом.

Но в цикле B следующий ход из X может вести сразу в B:

text
        ┌──> B
... → X
        └──> A   // старый безопасный маршрут

B ещё находится внутри тела, поэтому получаем fail.

Именно это происходит у тебя.

Особенно подозрителен этот фрагмент:

cpp
if (flag) {
    while (x < n) move('D');

    move('R');
    move('R');

    while (x > 2) move('U');

    if (y != m) move('R');

    ...
} else {
    while (y < m - 1) {
        while (x < n) move('D');
        move('R');
        while (x > 2) move('U');

        if (y != m - 1) move('R');
    }

    move('U');
    while (y > 1) move('L');
}

Обе ветки сами по себе задают некоторый порядок обхода клеток, но после

cpp
flag = (b == m);

программа может внезапно выбрать другую ветку сразу после появления нового яблока.

А после поедания яблока происходит важная вещь: хвост не двигается. Поэтому именно в момент new тело становится длиннее, а возможность безопасно менять порядок обхода становится ещё хуже.

Как обычно решают odd × odd: надо зафиксировать некоторую специальную клетку и использовать цикл на оставшихся n*m-1 клетках. Например, исключить угол (1,1).

Получается цикл длины n*m-1, потому что это чётное число. Змейка большую часть времени движется исключительно по этому циклу:

text
special = (1,1)

X → → → →
↑       ↓
↑ ← ← ← ↓
↑ → → → ↓
↑ ← ← ← ↓

X — исключённая клетка.

Ключевой инвариант:

пока тело не занимает почти всё поле, голова всегда движется только вперёд по одному фиксированному циклу.

Тогда столкновения невозможны.

Но возникает вопрос: что если яблоко появляется в исключённой клетке X?

Вот здесь и нужна специальная операция. Нельзя просто перейти на другой цикл. Нужно дождаться такой конфигурации, в которой можно безопасно сделать небольшой локальный detour:

text
... → A → B → ...
      |
      X

вместо

text
A → B

сделать

text
A → X → ... → B

или использовать маленький квадрат 2×2, чтобы встроить специальную клетку в текущий порядок движения.

Причём такую перестройку делают только в заранее известной безопасной фазе цикла, когда нужные клетки гарантированно не заняты телом.

Это принципиальное отличие от твоего:

cpp
if (b == m)
    маршрут_1();
else
    маршрут_2();

Нужно примерно:

cpp
if (apple_on_main_cycle) {
    continue_main_cycle();
} else {
    // яблоко в специальной клетке
    continue_main_cycle_until_safe_switch_point();
    perform_local_detour();
    return_to_main_cycle();
}

То есть новое яблоко определяет, что мы хотим сделать, но не обязательно что делаем следующим ходом.

Для понимания можно рассмотреть 3 × 3. Уберём центральную или угловую клетку и получим цикл по 8 клеткам. Например исключим центр:

text
(1,1) → (1,2) → (1,3)
  ↑                 ↓
(2,1)      X      (2,3)
  ↑                 ↓
(3,1) ← (3,2) ← (3,3)

Это прекрасный цикл:

text
(1,1)
(1,2)
(1,3)
(2,3)
(3,3)
(3,2)
(3,1)
(2,1)
(1,1)

Пока яблоки появляются на этих восьми клетках, можно просто бесконечно ходить по циклу. Рано или поздно каждое такое яблоко будет съедено.

Проблема только если яблоко появляется в центре (2,2). Тогда нужно в некоторый подходящий момент заменить кусок цикла, например

text
(2,3) -> (3,3)

на detour через центр, но так, чтобы сохранить допустимость тела. После съедания можно снова вернуться к безопасному циклическому порядку.

Для общего odd × odd удобнее не центр, а целая конструкция с одной «особой» клеткой возле края. Тогда локальное переключение можно реализовать через квадрат 2×2.

Например локально есть:

text
A B
C D

И основной цикл сейчас использует рёбра

text
A-B
C-D

В безопасный момент их можно заменить на

text
A-C
B-D

То есть происходит так называемый 2-switch:

text
A → B          A   B
    ...   =>   ↓   ↑
C ← D          C → D

Это позволяет менять форму гамильтонова пути/цикла без произвольного прыжка между двумя совершенно разными порядками.

Твою реализацию нечётного случая поэтому я бы не пытался чинить парой if-ов. Вот эта часть:

cpp
while (true) {
    if (b == m) flag = 1;
    else flag = 0;

    if (flag) {
        ...
    } else {
        ...
    }
}

архитектурно небезопасна.

Нужен инвариант вида:

cpp
// тело всегда является непрерывным отрезком
// одного фиксированного циклического порядка клеток

и любое отклонение от этого порядка должно быть маленьким, заранее доказанным и выполняться только в безопасной конфигурации.

То есть для трёх случаев хорошая структура решения такая:

cpp
if (n % 2 == 0) {
    // фиксированный гамильтонов цикл
}
else if (m % 2 == 0) {
    // фиксированный гамильтонов цикл
}
else {
    // фиксированный цикл по n*m-1 клеткам
    // + специальная обработка оставшейся клетки
}

А не два полноценных обхода, между которыми можно свободно переключаться.

Если хочешь именно довести твой код до AC, следующий полезный шаг — я могу построить конкретную корректную стратегию для odd × odd и дать готовый C++-код этой ветки else, совместимый с твоей функцией move().

Domanda

расскажи как строить стратегию для нечетного варианта и приведи код

Python

python
def build_cycle(n,m, mode):
    # mode 0: exclude A=(1,1), include B=(2,2)
    # base sequence for mode0
    seq=[(1,2)]
    # rows 2..n through cols1-2:
    r=2
    while r<=n-1:
        seq += [(r,2),(r,1),(r+1,1),(r+1,2)]
        r+=2
    # cols 3..m, rows 2..n serpentine
    # current should (n,2)
    currow=n
    for c in range(3,m+1):
        if currow==n:
            # step right at bottom then up to row2
            seq.append((n,c))
            for rr in range(n-1,1,-1):
                seq.append((rr,c))
            currow=2
        else:
            seq.append((2,c))
            for rr in range(3,n+1):
                seq.append((rr,c))
            cur

Pensiero

Constructed and validated the snake Hamiltonian cycle strategy

Worked for 3m 16s

Risposta

Для n и m нечётных можно сделать очень аккуратную стратегию с двумя почти одинаковыми циклами. Она проще и надёжнее твоего текущего переключения больших маршрутов.

Обозначим

cpp
A = (1, 1)
B = (2, 2)
G = (1, 2)
Q = (2, 1)

Строим два цикла длины n*m - 1:

text
C0: исключена A = (1,1)
C1: исключена B = (2,2)

Причём они полностью одинаковые, кроме маленького фрагмента:

text
C0:
G -> B -> Q

C1:
G -> A -> Q

То есть:

text
C0: (1,2) -> (2,2) -> (2,1) -> ...
C1: (1,2) -> (1,1) -> (2,1) -> ...

Вот это и позволяет безопасно переключаться.

1. Как выглядит основной цикл

Сначала рассмотрим C0, в котором отсутствует (1,1).

Для 5 × 5 начало обхода такое:

text
(1,2)
  ↓
(2,2) -> (2,1)
           ↓
(3,2) <- (3,1)
  ↓
(4,2) -> (4,1)
           ↓
(5,2) <- (5,1)
  ↓
(5,3)
  ↑
(4,3)
  ↑
(3,3)
  ↑
(2,3)
        -> (2,4)
             ↓
           (3,4)
             ↓
           (4,4)
             ↓
           (5,4)
        -> (5,5)
             ↑
           ...
             ↑
           (2,5)
             ↑
           (1,5)
             ←
           (1,4)
             ←
           (1,3)
             ←
           (1,2)

То есть получаем настоящий цикл через все клетки, кроме (1,1).

Программно он строится очень просто.

cpp
vector<pair<int,int>> build_cycle(int n, int m) {
    vector<pair<int,int>> p;

    p.push_back({1, 2});

    // Первые два столбца.
    // (2,2) -> (2,1) -> (3,1) -> (3,2) -> ...
    for (int r = 2; r < n; r += 2) {
        p.push_back({r, 2});
        p.push_back({r, 1});
        p.push_back({r + 1, 1});
        p.push_back({r + 1, 2});
    }

    // Столбцы 3..m змейкой, не заходя пока в первую строку.
    for (int c = 3; c <= m; c++) {
        if (c % 2 == 1) {
            p.push_back({n, c});
            for (int r = n - 1; r >= 2; r--)
                p.push_back({r, c});
        } else {
            p.push_back({2, c});
            for (int r = 3; r <= n; r++)
                p.push_back({r, c});
        }
    }

    // Возвращаемся по первой строке.
    p.push_back({1, m});
    for (int c = m - 1; c >= 3; c--)
        p.push_back({1, c});

    return p;
}

В этом vector ровно

cpp
n * m - 1

различных клеток. Единственная отсутствующая —

cpp
(1,1)

и последняя клетка (1,3) соседствует с первой (1,2), поэтому это цикл.

Критический кусок в начале:

text
(1,2) -> (2,2) -> (2,1)

Теперь строим второй цикл буквально заменой одной клетки:

text
(1,2) -> (1,1) -> (2,1)

То есть вместо (2,2) используем (1,1).

Получаем:

text
C0 исключает (1,1)
C1 исключает (2,2)

Все остальные n*m-2 клеток и их порядок совпадают.

2. Что делать с яблоками

Пусть сейчас двигаемся по C0.

Если яблоко находится где угодно, кроме (1,1), ничего делать не надо. Оно лежит на нашем цикле, поэтому мы просто продолжаем движение:

text
-> -> -> -> -> ...

и максимум за n*m-1 ходов его съедим.

А если яблоко появилось в исключённой клетке

text
(1,1)

мы продолжаем движение по C0, пока голова не придёт в

text
G = (1,2)

Вместо обычного

text
(1,2) -> (2,2) -> (2,1)

делаем

text
(1,2) -> (1,1) -> (2,1)

На первом ходе съедаем яблоко:

text
(1,2)
   |
   v
(1,1)

и одновременно переключаемся на C1.

После следующего хода:

text
(1,1) -> (2,1)

тело снова является обычным непрерывным отрезком цикла C1.

Теперь исключённой клеткой стала (2,2).

Если яблоко когда-нибудь появится там, делаем обратное переключение:

text
C1:
(1,2) -> (1,1) -> (2,1)

          ↓ переключение

C0:
(1,2) -> (2,2) -> (2,1)

Вот почему нужны именно две клетки по диагонали:

text
A G
Q B

то есть

text
A=(1,1)   G=(1,2)
Q=(2,1)   B=(2,2)

Мы фактически выбираем одну из двух диагоналей квадрата 2×2 как «пропущенную» клетку.

3. Почему столкновения не будет

Это главный инвариант:

Тело червя всегда является непрерывным отрезком текущего ориентированного цикла.

Представь цикл:

text
0 -> 1 -> 2 -> 3 -> ... -> K-1 -> 0

где

cpp
K = n * m - 1;

Если голова находится в i, тело расположено назад по циклу:

text
голова
   i
   ↓ назад
i-1
i-2
i-3
...
хвост

Поэтому следующий элемент i+1 не находится внутри тела.

Исключение — когда тело занимает вообще весь цикл. Тогда i+1 является хвостом, но по условию задачи в хвост двигаться разрешено.

Теперь рассмотрим переключение.

Допустим, работаем по C0, а яблоко в (1,1).

Перед переключением:

text
... тело ... -> G=(1,2)

а впереди по старому циклу:

text
G -> B -> Q

Мы вместо этого идём:

text
G -> A

A гарантированно свободна, потому что там яблоко.

После съедения тело становится:

text
A, G, ...

После этого нужно перейти

text
A -> Q

Если Q свободна — очевидно всё хорошо.

Есть только пограничный случай: тело до съедения имело длину K-1. Тогда после съедения длина становится K, а Q может оказаться хвостом.

Но это тоже разрешено правилами:

при ходе без яблока разрешается переместить голову в клетку, где непосредственно перед ходом находился хвост.

Причём новое яблоко не сможет появиться в Q, если Q сейчас хвост, потому что новые яблоки появляются только в свободных клетках.

Если же до съедения длина уже равна K=n*m-1, то исключённая клетка — единственная свободная клетка. Заходим в неё, длина становится n*m, интерактор сразу отвечает:

text
win

и второй ход вообще не понадобится.

Таким образом переключение безопасно при любой длине.

4. Готовый код нечётной ветки

Удобнее сначала построить next для двух циклов.

cpp
pair<int,int> nxt[2][11][11];

vector<pair<int,int>> build_cycle(int n, int m) {
    vector<pair<int,int>> p;

    // C0, исключена (1,1)

    p.push_back({1, 2});

    for (int r = 2; r < n; r += 2) {
        p.push_back({r, 2});
        p.push_back({r, 1});
        p.push_back({r + 1, 1});
        p.push_back({r + 1, 2});
    }

    for (int c = 3; c <= m; c++) {
        if (c % 2 == 1) {
            p.push_back({n, c});
            for (int r = n - 1; r >= 2; r--)
                p.push_back({r, c});
        } else {
            p.push_back({2, c});
            for (int r = 3; r <= n; r++)
                p.push_back({r, c});
        }
    }

    p.push_back({1, m});
    for (int c = m - 1; c >= 3; c--)
        p.push_back({1, c});

    return p;
}

void build_odd_cycles(int n, int m) {
    auto c0 = build_cycle(n, m);

    // C1 отличается только:
    // (1,2) -> (1,1) -> (2,1)
    // вместо
    // (1,2) -> (2,2) -> (2,1)
    auto c1 = c0;

    for (auto &[r, c] : c1) {
        if (r == 2 && c == 2) {
            r = 1;
            c = 1;
            break;
        }
    }

    int sz = c0.size();

    for (int i = 0; i < sz; i++) {
        auto [x1, y1] = c0[i];
        auto [x2, y2] = c0[(i + 1) % sz];
        nxt[0][x1][y1] = {x2, y2};
    }

    for (int i = 0; i < sz; i++) {
        auto [x1, y1] = c1[i];
        auto [x2, y2] = c1[(i + 1) % sz];
        nxt[1][x1][y1] = {x2, y2};
    }
}

Функция перевода соседних координат в команду:

cpp
char get_dir(int x1, int y1, int x2, int y2) {
    if (x2 == x1 - 1) return 'U';
    if (x2 == x1 + 1) return 'D';
    if (y2 == y1 - 1) return 'L';
    return 'R';
}

И сама стратегия:

cpp
void solve_odd(int n, int m) {
    build_odd_cycles(n, m);

    // mode = 0:
    // цикл исключает (1,1)
    //
    // mode = 1:
    // цикл исключает (2,2)

    int mode;

    // Начальная змея имеет длину 1.
    // Поэтому достаточно выбрать цикл,
    // который содержит стартовую клетку.
    if (x == 1 && y == 1)
        mode = 1;
    else
        mode = 0;

    while (true) {
        int hx, hy;

        if (mode == 0) {
            hx = 1;
            hy = 1;
        } else {
            hx = 2;
            hy = 2;
        }

        // Яблоко находится в единственной клетке,
        // которая не входит в текущий цикл.
        //
        // Переключаться можно только в G=(1,2).
        if (a == hx && b == hy && x == 1 && y == 2) {
            move(get_dir(x, y, hx, hy));

            // Старую "дыру" мы съели.
            // Теперь исключена другая диагональная клетка.
            mode ^= 1;

            continue;
        }

        auto [nx, ny] = nxt[mode][x][y];

        move(get_dir(x, y, nx, ny));
    }
}

Обрати внимание: отдельного

cpp
move(... до (2,1))

после переключения писать не надо.

После

cpp
mode ^= 1;

голова, например, находится в (1,1), а

cpp
nxt[1][1][1]

уже равно

cpp
(2,1)

поэтому следующая итерация сама сделает правильный ход.

5. Как вставить это в твой solve

Твоя структура может стать такой:

cpp
void solve() {
    int n, m;
    cin >> n >> m;

    cin >> x >> y;
    cin >> a >> b;

    if (n % 2 == 0) {
        // твоя стратегия для чётного n
        ...
        return;
    }

    if (m % 2 == 0) {
        // твоя стратегия для чётного m
        ...
        return;
    }

    // Оба нечётные
    solve_odd(n, m);
}

То есть весь твой нынешний последний огромный фрагмент:

cpp
if (a == 1 && b == 1) {
    ...
}

while (true) {
    if (b == m) flag = 1;
    ...
}

можно полностью удалить.

6. Ещё приятнее: старт вообще не надо приводить к (1,1)

Это важное отличие от твоего варианта.

Поскольку изначально длина червя равна 1, любая клетка автоматически является допустимым «отрезком цикла».

Если старт не (1,1), выбираем C0.

Если старт (1,1), выбираем C1.

После этого просто начинаем двигаться по nxt.

Например старт:

text
(4,3)

Нашли:

cpp
nxt[mode][4][3]

и сразу пошли по циклу.

Не требуется никаких:

cpp
while (x < n) ...
while (y > 1) ...

до начала основной стратегии.

7. Ограничение по ходам

Пусть

cpp
N = n * m <= 100.

В каждом состоянии текущий цикл имеет длину:

cpp
N - 1 <= 99.

До любого яблока на цикле нужно максимум N-1 ходов.

Если яблоко находится в исключённой клетке, максимум за N-2 ходов дойдём до (1,2) и ещё одним ходом съедим его.

То есть также максимум:

cpp
N - 1

ходов на яблоко.

Нужно съесть всего N-1 яблок, поэтому грубая верхняя оценка:

cpp
(N - 1)^2 <= 99^2 = 9801

ход.

Это намного меньше разрешённых 100000.

Итого стратегия имеет очень простой инвариант: в нечётном поле мы всегда ходим по циклу из nm-1 клеток; если яблоко попало в единственную исключённую клетку, в квадрате 2×2 меняем, какая из двух диагональных клеток исключена. Именно локальность этого переключения делает конструкцию безопасной.

Condividi questa Q&A