Описание проблемы находится здесь и нажмите здесь, чтобы увидеть все другие мои решения Эйлера на F#.
Это более сложная версия задачи 82, и теперь вы можете двигаться во всех четырех направлениях!
Как и раньше, мы начинаем с загрузки входных данных в 2D-массив:
и инициализируйте другую матрицу того же размера, чтобы содержать минимальную сумму, ведущую к каждой ячейке:
Однако на этот раз мы сделали по-другому, так это выбрали начальные значения по умолчанию:
- для верхнего левого угла (0, 0) минимальная сумма сама
- для всех остальных ячеек в (row, col) мы всегда будем перемещаться вправо, а затем вниз
- если row = 0, то это равносильно движению только вправо, пока мы не достигнем col
- если col = 0, то это равнозначно перемещению вниз только до тех пор, пока мы не достигнем row
e.g.
Далее, как и для задачи 82, мы добавим пару помощников, которые помогут нам пройти по обеим матрицам:
и мы найдем новую минимальную сумму для каждой ячейки, взяв минимум из четырех направлений:
В отличие от предыдущего, мы не можем изолировать оптимизацию одного столбца за раз, и вместо этого нам нужно будет пройти всю матрицу. Для лучшей локализации кэша мы сначала пройдем по строке и рекурсивно оптимизируем всю матрицу до тех пор, пока дальнейшая оптимизация не станет невозможной:
Наконец, найдите окончательное значение для нижнего правого угла матрицы суммы:
Это решение работает на моем ноутбуке за 73 мс.
Исходный код этого решения находится здесь.
