Разбор задачи «Контроль возврата автономного робота»

Идея задачи

Робот начинает движение из точки (0, 0) и выполняет команды:

• U — вверх,
• D — вниз,
• L — влево,
• R — вправо.

Нужно определить, окажется ли он снова в точке старта после выполнения всей строки команд.

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

Что происходит при каждой команде

Будем хранить две переменные:

• x — координата по горизонтали,
• y — координата по вертикали.

Изначально:

x = 0, y = 0

Дальше для каждого символа:

• U → y += 1
• D → y -= 1
• L → x -= 1
• R → x += 1

После обработки всей строки:

• если x == 0 и y == 0, то робот вернулся в начало;
• иначе не вернулся.

Почему этого достаточно

Каждая команда изменяет положение робота ровно на 1 в одном из направлений. Значит, итоговое положение полностью определяется количеством шагов вверх, вниз, влево и вправо.

Чтобы робот вернулся в начало, должны одновременно выполняться два условия:

• число ходов вверх должно компенсироваться числом ходов вниз;
• число ходов вправо должно компенсироваться числом ходов влево.

Хранение координат x и y как раз и учитывает этот баланс автоматически.

Пошаговый пример

Пусть дана строка:

URDL

Тогда:

1. U → (0, 1)
2. R → (1, 1)
3. D → (1, 0)
4. L → (0, 0)

В конце робот снова в начале, значит ответ YES.

Ещё пример:

LL

1. L → (-1, 0)
2. L → (-2, 0)

В точку (0, 0) робот не вернулся, значит ответ NO.

Алгоритм

1. Считать строку команд.
2. Завести x = 0, y = 0.
3. Пройти по всем символам строки.
4. Для каждого символа изменить координаты по правилу направления.

5. После цикла проверить:

   • если x == 0 и y == 0, вывести YES;
   • иначе вывести NO.

Доказательство корректности

Докажем, что алгоритм всегда выводит правильный ответ.

Рассмотрим обработку строки команд слева направо. После обработки каждого символа переменные x и y равны реальным координатам робота после выполнения соответствующего префикса команд:

• для пустой строки это верно, потому что робот стартует в (0, 0);
• если после нескольких команд координаты посчитаны верно, то следующая команда меняет ровно одну координату на ±1, и алгоритм делает то же самое.

Значит, после обработки всей строки значения x и y совпадают с итоговым положением робота.

Теперь:

• если итоговые координаты равны (0, 0), робот вернулся в начальную точку, и алгоритм выводит YES;
• если итоговые координаты отличаются от (0, 0), робот не вернулся, и алгоритм выводит NO.

Следовательно, алгоритм корректен.

Оценка сложности

Пусть длина строки равна n.

Мы один раз проходим по всем символам, поэтому:

• время работы: O(n);
• дополнительная память: O(1).

Это оптимальное решение, потому что как минимум каждый символ нужно прочитать.

Типичные ошибки

1. Пытаться хранить весь путь

Это не нужно. Для ответа важна только итоговая позиция.

2. Перепутать изменения координат

Нужно внимательно соблюдать соответствие:

• U → y + 1
• D → y - 1
• L → x - 1
• R → x + 1

3. Проверять только одну координату

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

Решение на C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;

    int x = 0, y = 0;

    for (char c : s) {
        if (c == 'U') y++;
        else if (c == 'D') y--;
        else if (c == 'L') x--;
        else if (c == 'R') x++;
    }

    if (x == 0 && y == 0) cout << "YES\n";
    else cout << "NO\n";

    return 0;
}

Пояснение к коду на C++

• Считываем строку s.
• Переменные x и y отвечают за положение робота.
• В цикле обрабатываем каждую команду.
• В конце сравниваем координаты с (0, 0).

Решение на Python

s = input().strip()

x = 0
y = 0

for c in s:
    if c == 'U':
        y += 1
    elif c == 'D':
        y -= 1
    elif c == 'L':
        x -= 1
    elif c == 'R':
        x += 1

if x == 0 and y == 0:
    print("YES")
else:
    print("NO")

Пояснение к коду на Python

Логика полностью совпадает с C++-версией:

• читаем строку,
• обновляем координаты,
• проверяем, вернулся ли робот в начало.

Альтернативный взгляд

Можно мыслить не через координаты, а через баланс направлений:

• сколько раз встретилось U и D;
• сколько раз встретилось L и R.

Если:

count(U) == count(D)
count(L) == count(R)

то ответ YES, иначе NO.

Но вариант с координатами обычно удобнее и естественнее, потому что он сразу моделирует движение.