CODEWITHSUNDEEP
algorithmgraph-theorydynamic-programming
Rushil Paul
Rushil Paul

Reputation: 2048

Algorithmic approach - Find the best path in a grid

Question: There is an m x n grid ( 0 <= m, n <= 500). Each cell in the grid contains k coins (k could be negative or 0 too). You start from 0, 0 and end at m-1, n-1, and you can move either 1 step down or 1 step right, collecting as many coins as you can. If k < 0, then that particular cell has a robber and you can't move into that cell. If you move into any of the 8 neighboring cells, you will be robbed of k coins. How many coins will you have when you reach m-1, n-1 ?

For example in the grid:

0,23,20,-32
13,14,44,-44
23,19,41,9
46,27,20,0

ans = 129 (by following the path: 0-13-23-46-27-20-0)

Time limit: 5 sec

I don't think this program can be solved using dynamic programming. And I haven't studied graph theory (in case it could be used to solve this problem). The straightforward recursive approach is the only thing I can think of, which is too inefficient under the given constraints.

So what would be a good approach to solve it? Don't just post code, tell me how to begin. If its related to graph theory, then indicating which theorem is involved would be very useful.

Upvotes: 3

Views: 4220

Answers (3)

NiklasMM
NiklasMM

Reputation: 2972

Your problem could be described as a max-flow problem and thus be solved by the Ford-Fulkerson-Algorithm.

Transformation goes as follows:

  • Delete the negative nodes and subtract their amount from the neighboring cells.
  • 0/0 would be the source, m-1, n-1 the sink
  • Each node gets connected to the one below and to the right, the capacity of the arc equals the value of its target node.
  • Now the max flow equals the maximum amount of coins you can have

There may be easier solutions, this is just the first thing that came to my mind.

Edit: As dasblinkenlight points out in the comments, this will not work, because a flow is actually the combination of multiple paths, which is of course not what we want here.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727077

I don't think this program can be solved using dynamic programming.

Why not? This is a prime candidate for the dynamic programming approach.

The straightforward recursive approach is the only thing I can think of, which is too inefficient under the given constraints.

Can you build a recursive solution that solves, say, a 5x5 grid? Perfect! Start with that, and then memoize it by adding an MxN array of best results for cells which you have already solved. Start that array with all large negative values, and then update it when you find a solution that is better. than what's there already. Once you 've finished with the cell, put the solution into the MxN array: the next time you come there recursively, check the array for a number, and if a value is there, return it without continuing with the recursion.

The memoized solution itself is rather straightforward. The preprocessing step of the algorithm (subtracting negative numbers from neighboring cells) takes more code.

int solve(int r, int c) {
    if(memo[r][c] != MIN) {
        return memo[r][c];
    }
    int res = grid[r][c];
    int a = 0, b = 0;
    if (r+1 != R) {
        a = solve(r+1, c);
    }
    if (c+1 != C) {
        b = solve(r, c+1);
    }
    res = max(res+a, res+b);
    return memo[r][c] = res;
}

Here is the solution on ideone, it returns 129 as expected.

Upvotes: 4

Mark Byers
Mark Byers

Reputation: 839224

Your problem is called the longest path problem for a weighted directed acyclic graph.

The most number of coins you can have when you reach (x,y) is given by:

coins(x,y) = max(coins(x-1,y), coins(x,y-1)) + change

This is a recurrence relationship. It can be solved either by using recursion and memoization for performance, or by using an iterative algorithm.

The iterative algorithm is to work through the grid one diagonal at a time. Start at 0,0. Then calculate 0,1 and 1,0. Then 0,2 and 1,1 and 2,0. etc...

Step 1:

 0,  ?,  ?,  ?
 ?,  ?,  ?,  ?
 ?,  ?,  ?,  ?
 ?,  ?,  ?,  ?

Step 2:

 0, 23,  ?,  ?
13,  ?,  ?,  ?
 ?,  ?,  ?,  ?
 ?,  ?,  ?,  ?

Step 3:

 0, 23,-33,  ?
13, 37,  ?,  ?   // 37 because of max(23,13) + 14
36,  ?,  ?,  ?
 ?,  ?,  ?,  ?

etc...

When you complete this process, the answer is the number in the bottom-right corner.

Upvotes: 4

Related Questions