MiddleКодИногдаЕщё не отвечали
Сократить путь L/R/U/D, вырезая замкнутые подмаршруты
Путь — список единичных шагов: L, R, U, D. Удалите любой замкнутый подмаршрут — отрезок шагов, возвращающий в уже посещённую координату, — чтобы результат шёл тем же реальным маршрутом, но без лишних петель.
Требования:
- Сохраняйте маршрут, а не только итоговое смещение:
[D,R,U]остаётся[D,R,U]. [R,D,L,U,R]превращается в[R](средние четыре возвращают в старт).
std::vector<char> shorten(const std::vector<char>& moves) {
// ваш код здесь
}Допишите реализацию.
Идём по шагам, отслеживая текущую координату (x, y) и хеш-таблицу каждой посещённой координаты к её позиции в выходе. Когда координата повторяется, шаги с её первого посещения образуют замкнутую петлю: усекаем выход до той позиции и убираем координаты, добавленные между.
- ✗Сводить к итоговому смещению, что теряет форму реального маршрута
- ✗Гасить только соседние развороты, пропуская крупные петли вроде R,D,L,U
- ✗Забыть засеять стартовую координату на индексе 0 выхода
- →Почему итоговое смещение даёт неверный ответ для
[D,R,U]? - →Как стирать промежуточные координаты из таблицы при усечении?
Оглавление
Задача
Удалите из пути L/R/U/D замкнутые подмаршруты, сохранив реальный маршрут. За O(n).
Решение
#include <vector>
#include <unordered_map>
#include <cstdint>
std::vector<char> shorten(const std::vector<char>& moves) {
auto key = [](int x, int y){ return (int64_t(x) << 32) ^ uint32_t(y); };
std::unordered_map<int64_t, int> seen; // координата → индекс в out
std::vector<char> out;
int x = 0, y = 0;
seen[key(0, 0)] = 0; // старт
for (char m : moves) {
if (m == 'L') --x; else if (m == 'R') ++x;
else if (m == 'U') ++y; else --y;
auto it = seen.find(key(x, y));
if (it != seen.end()) { // координата повторилась → петля
for (int i = it->second + 1; i < (int)out.size(); ++i) {
/* пересчитать и стереть промежуточные координаты */
}
seen.clear(); int cx = 0, cy = 0; // перестроить карту по out
seen[key(0, 0)] = 0;
out.resize(it->second); // усечь до повтора
for (int i = 0; i < (int)out.size(); ++i) {
char c = out[i];
if (c=='L') --cx; else if (c=='R') ++cx; else if (c=='U') ++cy; else --cy;
seen[key(cx, cy)] = i + 1;
}
x = cx; y = cy;
} else { out.push_back(m); seen[key(x, y)] = (int)out.size(); }
}
return out;
}Ключевые моменты
- Хеш-карта координата → индекс находит повтор и место усечения.
- Сохраняем реальный маршрут, а не итоговое смещение.
- Гасить только соседние развороты недостаточно для крупных петель.
Оглавление
