Все записи категории ‘На первой полосе’

Решаем задачу с литкода №1575 Count All Possible Routes.

Дан массив чисел, описывающий города. Указаны индексы стартового города (start) и города, куда нужно приехать (finish), а также запас топлива (fuel). Требуется найти кол-во путей, по которым можно добраться до города-назначения, при заданном запасе топлива.

Перемещение между городами стоит некоторых затрат топлива. В данной задаче указывается, что затраты топлива определяются модулем разницы между числами, описывающими пару городов.

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

Формулируется задача так: дан массив интервалов, каждый из которых определен двумя числами — [начало интервала, конец интервала]. Требуется удалить минимальное число элементов, чтобы интервалы не перекрывали друг друга.

Продолжаем разбор классических задач по программированию. На этот раз лабиринтовая задача, которая формулируется так — дан плоский лабиринт в виде двумерного массива, где стенка отмечена 1, а свободный участок как 0. Также дана начальная позиция игрока, точка входа — [row, column] — как координаты в лабиринте.

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