Максимальная сумма пути от левого столбца до правого столбца

Question

Я пытаюсь вычислить максимальную сумму, которая может быть достигнута при переходе от левого столбца в правый столбец в сетке. Разрешенные движения вверх, вниз, вправо. Я реализовал это решение (это поиск в ширине):

for(int i=1; i<=n; i++) { 
    Queue<Position> q = new LinkedList<Position>(); 
    q.add(new Position(i, 1)); 
    dp[i][1] = map[i][1]; 

    while(!q.isEmpty()) { 
     Position node = q.poll(); 
     visited[node.n][node.m] = 1; 
     if(dp[node.n][node.m] > max) { 
      max = dp[node.n][node.m]; 
     } 
     if(visited[node.n-1][node.m] != 1 && node.n != 1 && dp[node.n-1][node.m] < dp[node.n][node.m] + map[node.n-1][node.m] && map[node.n-1][node.m] != -1) { 
      dp[node.n-1][node.m] = dp[node.n][node.m] + map[node.n-1][node.m]; 

      q.add(new Position(node.n-1, node.m)); 
     } 
     if(visited[node.n+1][node.m] != 1 && node.n != n && dp[node.n +1][node.m] < dp[node.n][node.m] + map[node.n+1][node.m] && map[node.n+1][node.m] != -1) { 
      dp[node.n +1][node.m] = dp[node.n][node.m] + map[node.n+1][node.m]; 
      q.add(new Position(node.n + 1, node.m)); 
     } 
     if(visited[node.n][node.m+1] != 1 && node.m != m && dp[node.n][node.m+1] < dp[node.n][node.m] + map[node.n][node.m+1] && map[node.n][node.m+1] != -1) { 
      dp[node.n][node.m+1] = dp[node.n][node.m] + map[node.n][node.m+1]; 
      q.add(new Position(node.n, node.m+1)); 
     } 

    } 
} 
static class Position { 
     int n, m; 
     public Position(int row, int column) { 
      this.n = row; 
      this.m = column; 
     } 
    } 

Пример ввод:

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

Проблема с моим решением он должен достичь 2 (в последнем ряде 2-й колонке), следуя- -> 3-> 3-> 2, но мое решение поместило 2 в состояние посещения, чтобы оно не проверял. И если я удаляю посещенный массив, он попадает в бесконечный цикл вверх, вниз, вверх, вниз по любой ячейке.

Редактировать: Каждый пункт можно посетить только один раз.

Answer 1

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

Чтобы решить эту проблему, однако можно отметить, что в данной позиции (x, y) вы либо

• только что прибыл в (x, y) из (x-1, y) и, следовательно, вам разрешено идти вверх, вниз или вправо (если вы не на края, конечно)
• прибыл в (x, y) из (x, y-1) (т.е. сверху), а затем вы позволили только идти вниз или вправо
• прибыл в (x, y) из (x, y+1) (т.е. снизу) и й ан вам разрешено только идти вверх или вправо

Это приводит непосредственно в следующей рекурсивной-memoized решения (код в Python):

matrix = [[-1, 4, 5, 1], 
      [ 2,-1, 2, 4], 
      [ 3, 3,-1, 3], 
      [ 4, 2, 1, 2]] 
rows = len(matrix) 
cols = len(matrix[0]) 
cache = {} 

def maxsum(dir, x, y): 
    key = (dir, x, y) 
    if key in cache: return cache[key] 
    base = matrix[y][x] 
    if x < cols-1: 
     best = base + maxsum("left", x+1, y) 
    else: 
     best = base 
    if dir != "above" and y > 0: 
     best = max(best, base + maxsum("below", x, y-1)) 
    if dir != "below" and y < rows-1: 
     best = max(best, base + maxsum("above", x, y+1)) 
    cache[key] = best 
    return best 

print(max(maxsum("left", 0, y) for y in range(rows))) 

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