Наименьший самый длинный возрастающий путь
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Матрицы и сетки
- Динамическое программирование
- Деревья и графы
Дана прямоугольная таблица целых чисел. Путь начинается в любой клетке и каждым шагом переходит в соседнюю по стороне клетку (вверх, вниз, влево или вправо, не выходя за границы), причём каждое следующее число строго больше предыдущего. Найдите путь наибольшей длины и верните список чисел, через которые он проходит, по порядку. Если таких путей несколько, верните тот, чей список чисел лексикографически наименьший (сравнение по первому различающемуся числу). Для пустой таблицы (без строк или со строками нулевой длины) верните [].
В таблице до 10 000 клеток, числа от -10⁹ до 10⁹. Перебор всех путей на больших тестах не уложится во время.
Пример: [[3, 4, 5], [3, 2, 6], [2, 2, 1]] → [2, 4, 5, 6] (длину 4 имеет и путь 3, 4, 5, 6, но он лексикографически больше).
Источник: задача CodeShare