Algorithm - Longest Path Grid Puzzle

Question

So the situation is:
1. There is NxN grid so it's a square grid
2. There will be a maximum amount of step that will be given
3. Every cell inside the grid have certain amount of value that will reduce the maximum amount of step
4. We can only move to right and below.
5. The starting point is top left of the grid and the goal is the bottom right of the grid.
6. We need to determine the longest path ( The one with least maximum amount of step left )
7. If there is no path possible the result will -1

So currently I already wrote a code that will work with some case but still not the optimum one.
What I'm doing right now are :
1. Check if the next right value and next below value.
2. Go to the bigger value.
3. If the Maximum amount of step become 0 backtrack to previous cell and move to another direction.
4. If the right value and below value is same I will check the next cell after the next cell.

Looks like the problem is with the 4th point.

this is my code for the 4th point :

private static int determineBestNext(int[][] grid, int currentX, int currentY) {
    int nextRight = 0;
    int nextBelow = 0;
    int numberOfRows = grid.length - 1;
    for(int i=currentX+1;i<numberOfRows-1;i++) {
        nextRight += grid[currentY][i+1];
        if(currentY != numberOfRows) {
            nextRight += grid[currentY+1][i+1];
        }
    }
    for(int i=currentY+1;i<numberOfRows-1;i++) {
        nextBelow = grid[i+1][currentX];
        if(currentX != numberOfRows) {
            nextBelow += grid[i+1][currentX+1];
        }
    }
    if(nextRight > nextBelow) {
        return 1;
    } else if (nextBelow > nextRight) {
        return 2;
    } else {
        return determineBestNext(grid, currentX+1,currentY+1);
    }
}

I guess the fallback is when the X is bigger than Y the number of step in Y is bigger so the chance Right value will be bigger than X and vice versa.

Do you guys have another idea? Thanks!

Thanks!

Answer 1

You can find the best path in O(n^2). I will call (1,1) the top left cell (the start point) and grid(i,j) will be the value of the cell. And steps(i,j) is the minimal number of steps necessary to get to the cell(i,j).

You can quickly identify the relation

steps(i,j) = min(steps(i-1,j), steps(i,j-1)) + grid(i,j)  // if i,j > 1

If i = 1 or j = 1 or i = j = 1 it's even easier, because then there's only one possible path.

So we want to calculate steps(N,N), we get steps(N,N) = min(steps(N-1,N), steps(N,N-1)) + grid(N,N). For the calculation we need steps(N-1,N) and steps(N,N-1). So steps(N-1,N) = min(steps(N-2,N), steps(N-1,N-1)) + grid(N-1,N) and steps(N,N-1) = min(steps(N-1,N-1), steps(N,N-2)) + grid(N,N-1). We see that for each of this result we need the value of steps(N-1,N-1). It would be a waist, to calculate this value twice. If we calculate it only one and remember the value, we can save one calculation. These things happen quite often.

The best way to remember is to have a fixed order of evaluation. Here's some pseudo code:

function getBestPath(grid, N)
    steps = new N x N int-array //initialized with 0

    //first row
    steps[0][0] = grid[0][0] 
    // only one path to get to (0,0), it's doing nothing
    for (i = 1; i < N; i++)
        steps[0][i] = steps[0][i-1] + grid[0][i] 
        // only one path each, just going right

    //other rows
    for (row = 1; row < N; row++)
        steps[row][0] = steps[row-1][0] + grid[row][0] 
        //only one way to get to (row,0), only go down

        for (i = 1; i < N; i++)
            steps[row][i] = min(steps[row-1][i], steps[row][i-1]) + grid[row][i]

    return steps[N-1][N-1]

Answer 2

Point 7 makes me think you are missing out on some detail.

When is no path possible? Is the assumption that the amount of step needs to be non-negative?

If not, then a path is always possible, and an easy dynamic programming O(N^2) algorithm is possible, as the other answer tells you.

Are you trying to cheat on some programming test by modifying the problem and missing out important details in the process?