Сборка заказа на складе с маленькой тележкой
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Матрицы и сетки
- Деревья и графы
- Динамическое программирование
Карта склада дана списком строк grid одинаковой длины: # — стеллаж, . — проход, S — пункт упаковки (ровно один), * — товар, который нужно собрать (не больше 8 товаров). Сборщик начинает в S с пустой тележкой. Каждый шаг ведёт в соседнюю клетку сверху, снизу, слева или справа, которая лежит на карте и не занята стеллажом; клетки с товарами и пункт упаковки проходимы.
Стоя на клетке товара, сборщик может положить его в тележку, если в ней меньше capacity товаров (capacity ≥ 1); проходить по товару, не беря его, можно. В пункте упаковки тележка разгружается. Верните наименьшее число шагов, после которых все товары доставлены в пункт упаковки (сборщик заканчивает в S с пустой тележкой). Верните 0, если товаров нет, и -1, если до какого-то товара от пункта не добраться. Карта не больше 20 × 20.
Пример: ["*..#*", ".#...", "S..*."], capacity = 2 → 16 (один рейс в 4 шага за левым верхним товаром и один рейс в 12 шагов за двумя остальными).
Источник: задача CodeShare