Интересный лабиринт

Question

У нас есть лабиринт R X C, где 1 < = R, C < = 500. Этот лабиринт заполнен числами от -1 до 100. Теперь игра выглядит следующим образом:

Где когда-либо есть -1 в квадрате, предположим, что это камень преткновения в , что клетка, и вы не можете двигаться Повсеместно эта клетка. Вы можете начать с любой ячейкой в ​​1-й колонке (конечно, которая не имеет -1) и выйти из в любую ячейку из последнего столбца. Вы можете перемещаться вверх, вниз, вправо. Как вы двигаетесь, u собирайте числа в ячейке, кроме -1, которые обозначают большой камень, который находится в нашем лабиринте. Каждая ячейка должна посещаться только .

Каков путь слева направо, где вы можете выбрать максимальную сумму чисел? ЛЕГКО !! Dp может делать магию Но Но ... вот улов - Правило 5.

Мы можем выйти из лабиринта, если мы сможем достичь первого или нижнего ряда. Но затем 2 вещи случаются:

a) Мы теряем все собранные до сих пор пункты.

b) мы располагаем лабиринт в той же колонке, но в противоположной ячейке.

ex: рассмотрите лабиринт 3X3 (1-indexed). поэтому, если мы доберемся, (1,2), мы можем выйти оттуда и потерять все точки и войти (3,2), и игра продолжается ....

Теперь мы должны найти путь с оценкой maxiumum ,

Я не могу видеть, как мы можем захватить это прыгание и обратно в лабиринте путем динамического программирования? Кроме того, каждый раз, когда мы это делаем, мы должны делать оценку «0».

Пример:

рассмотреть лабиринт:

-1 4 5 1 
2 -1 2 4 
3 3 -1 -1 
4 2 1 2 

ответ = 16.

(4,1) -> (4,2) -> (1,2) -> (1,3) -> (2,3) -> (2,4) -> (1,4)

Answer 1

Запустите тот же алгоритм, что и у вас. После того, как вы закончите проверку столбца, если доступны верхние/нижние позиции (есть путь, чтобы попасть туда, и они не заблокированы).

Если один из них доступен, а другой не предполагается, вы можете добраться до недоступного с предыдущим счетом 0 (в основном запустите вычисление, но предположите, что ячейка в предыдущем столбце имеет счет 0).

Если нет, то ничего не поделаешь.

Если оба доступны, так как у вас есть положительный результат во всем мире, нет смысла что-то понижать> 0 и начинать с 0 снова.

Answer 2

Вы должны быть в состоянии получить список решений (без прохождения через -1) из

A) Left -> Right 
B) Top -> Right 
C) Bottom -> Right 

Тогда вы должны также быть в состоянии получить список путей из (без -1)

D) Left -> Top 
E) Left -> Bottom 

Из списка (B) удалите все, у которых нет пути соединения из списка (D). Из списка (C) удалите все, у которых нет пути подключения из списка (E).

Затем выбрать самое высокое разрешение из A, B, C.