Глючний робот (Розбір)

Нехай кінцева позиція робота без пропуску жодного ходу дорівнює (X, Y). Мангеттенська відстань дорівнює |X| + |Y|.

Коли ми пропускаємо один хід, наприклад хід типу U (Вгору), сумарне зміщення вздовж осі $y$ зменшується на 1. Отже, нова кінцева позиція стає (X, Y-1).

Оскільки порядок додавання векторів комутативний, не має значення, який саме хід U ми пропустимо; кінцевий результат буде однаковим. Тому нам потрібно перевірити лише до 4 сценаріїв:

1. Пропустити одну U (якщо вона є): нова відстань = |X| + |Y-1|.

2. Пропустити одну D (якщо вона є): нова відстань = |X| + |Y+1|.

3. Пропустити одну R (якщо вона є): нова відстань = |X-1| + |Y|.

4. Пропустити одну L (якщо вона є): нова відстань = |X+1| + |Y|.

Ми обчислюємо відстань для випадку "Без пропуску" та для цих 4 конкретних випадків, а потім виводимо максимум. Складність: $O(|S|)$ на зчитування рядка, $O(1)$ на перевірку 4 варіантів.