CODEWITHSUNDEEP
algorithmdata-structuresgraphdynamic-programming
crysis
crysis

Reputation: 1584

Maximum sum of path from left column to right column

I'm trying to calculate the maximum sum that can be achieved in going from left column to right column in a grid. Allowed movements are up, down, right. I've implemented this solution (it's Breadth First Search) :

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;
        }
    }

Example Input:

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

The problem with my solution is it should reach 2 (in last row 2nd column) by following 4->3->3->2 but my solution put 2 in visited state so it won't check it. And if I remove visited array, it will get trapped in infinite loop of up, down, up, down on any cell.

Edit : Each point can be visited only once.

Upvotes: 1

Views: 2065

Answers (1)

6502
6502

Reputation: 114461

This problem can be solved with a linear programming approach, but there is a small twist because you cannot visit each cell more than once but the movements can actually take you to that condition.

To solve the issue you can however note that in a given position (x, y) you either

  • just arrived at (x, y) from (x-1, y) and therefore you are allowed to go up, down or right (unless you're on the edges, of course)
  • arrived at (x, y) from (x, y-1) (i.e. from above) and then you're allowed only to go down or right
  • arrived at (x, y) from (x, y+1) (i.e. from below) and then you're allowed only to go up or right

This translates directly in the following recursive-memoized solution (code is in 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)))

If you are not allowed to step over a negative value (even if that would guarantee a bigger sum) the changes are trivial (and you need to specify what to return if there are no paths going from left column to right column).

Upvotes: 1

Related Questions