Задача о последнем дне переправы по льду

Задачу можно сформулировать так: представьте себе участок реки покрытый льдом и в первый день он полностью скован крепким льдом, позволяющим переправится по любому его участку. Разбив участок реки на R x C секторов, мы заявляем, что каждый день очередной сектор из сетки R x C становится не безопасным для пересечения. Нужно определить последний день, когда реку еще можно перейти по крепкому льду.

Да это, кстати, задача #1970 Last Day Where You Can Still Cross с литкода.

Строки (R) cекторов расположены вдоль русла реки, т.е. надо перебраться с r = 1 на r = R. В задаче даны R, С и массив опасных участков по дням [[ri, ci]], где i — это номер очередного дня.

Решение

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

Т.е. алгоритм следующий — взяли день из середины текущего диапазона, проверили — можно ли пересечь реку в текущей ситуации. Если можно, то запомнили результат, и левую границу поискового окна сдвинули в середину. Иначе правую границу сдвинули в середину.

Проблема поиска пути

Граничные условия задачи предполагают, что R и C могут достигать 104. Это значит, что нужно как то оптимизировать поиск. Вместо поиска безопасного пути через реку, я буду смотреть нельзя ли прочертить путь вдоль реки по опасным участкам, т.к. именно они нам доступны как исходные данные. Если такой путь существует, то пересечь безопасно реку нельзя.

Давайте посмотрим детали реализации (TS).

Судя по статистике, это довольно эффективное решение (сравнивал среди JS решений), т.к. TS решений было недостаточно для показа графика.

Сложнее всего, наверное, было психологически отказаться от традиционного использования массива-карты для поиска пути. Но вместо него пришлось использовать объект Set, т.к. нам нужно эффективно находить подходящие ячейки для следующего ходя, без перебора массива вручную.

Написать комментарий

Мало букафф? Читайте есчо !

Задача о поиске всех подходящих под-сум

Июль 1, 2023 г.

№560 leetcode Subarray Sum Equals K. Есть массив чисел, и дано значение k. Надо найти все последовательные под-массивы сумма которых равна k. В условиях также сказано, что числа в массиве могут быть как положительные, так и отрицательные. Если ...

Читать

Задача: подсчитать варианты размена монет

Август 11, 2023 г.

Снова классика задач на перебор вариантов - есть номиналы монет, требуется найти все варианты размена указанной суммы. Число монет каждого номинала - не ...

Читать

 

Комментарии к «Задача о последнем дне переправы по льду»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: