CODEWITHSUNDEEP
algorithm
Gerard
Gerard

Reputation: 679

How to traverse a grid using two different paths to maximize the sum of the path?

I have an N by N grid, with values in each box. I have to move from the top-left corner to the bottom-right corner (path 1) and from the top-right corner to the bottom-left (path 2). When I move from top-left to bottom-right I can only move down or to the right. Likewise, when I move from the top-right to the bottom-left I can only move left and down.

But if I move down while taking path 1, the corresponding move for path 2 should be to the left. Similarly, if I move right while taking path 1, the corresponding move for path 2 should be down.

As we take both paths, we sum up the values we encounter in each box. What is the maximum value we can obtain?

Consider as an example the following grid:

 6   0   3  -1

 7   4   2   4

-3   3  -2   8

13  10  -1  -4

The best paths we can take are represented as follows: path one is represented by a *, while path 2 by a ~. 

(6*)  (0)   (3~)  (-1~)

(7*)  (4*~) (2~)  (4)

(-3)  (3*~) (-2*) (8*)

(13~) (10~) (-1)  (-4*)

The sum for both of these paths is 56.

We have to devise an algorithm to compute the maximum possible score given an arbitrary N by N grid.

It was pretty clear that this was a DP problem. So, I tried to identify a recurrence relation, so to speak. I tried using the recurrence relation from the classic problem of finding the maximum sum over all paths in an N by M grid, but that didn't work because it just got too complicated.

I tried to divide the N by N grid into four (N-1) by (N-1) grids that overlap, so demonstrating this in a 3 by 3 grid:

a1 a2 a3

a4 a5 a6

a7 a8 a9

I divided this into four 2 x 2 grids:

a1 a2  ,   a2 a3   ,   a4 a5   ,  a5 a6

a4 a5  ,   a5 a6   ,   a7 a8   ,  a8 a9

Assuming we know the best paths for all these grids, can we then compute the best path for the larger grid?

Well, this seemed promising, but I quickly found out that these recurrence relations, were dependent on the larger case. For example,

If we consider the second 2 x 2 grid, assuming we know the best path 1 and path 2 = S. Now, clearly, for us to get from a1 to a2, we need to move right, but this means that the first move in the sub case (the first move in path 2) should be to the down, which isn't guaranteed.

How do we solve this?

Upvotes: 1

Views: 1142

Answers (2)

Jeff Snider
Jeff Snider

Reputation: 750

The rules for moving the two points are equivalent to finding a single path through a grid which is a sum of your grid and itself rotated -90 degrees (90 degrees to the left / counterclockwise / anti-clockwise, depending on your locale).

"Down" for the top-left point corresponds to "Left" for the top-right point, which when rotated -90 degrees is down. "Right" for the top-left point corresponds to "Down" for the top-right point, which when rotated -90 degrees is right. (Got it?)

So your example grid is

 6-1   0+4   3+8  -1-4        5   4  11  -5

 7+3   4+2   2-2   4-1       10   6   0   3
                          =
-3+0   3+4  -2+3   8+10      -3   7   1  18

13+6  10+7  -1-3  -4+13      19  17  -4   9

You can now find a path from top-left to bottom-right by any of the usual means. In fact, you don't need the path, just the maximal sum, which is easier: collapse the matrix from top-left down by addition. The initial condition is the above grid. The next step is to add the top left value to its valid neighbors:

     9  11  -5

15   6   0   3

-3   7   1  18

19  17  -4   9

Then pick the larger of the two neighbors for any grid point with two valid neighbors (here 21 is larger than 20 and 12):

        20  -5

    21   0   3

12   7   1  18

19  17  -4   9

And so on...

            15

        21   3              24
                ->                  
    28   1  18           29 18     ->        47
                                                    ->  
31  17  -4   9        48 -4  9            44  9            56

I have just solved your 4x4 case by hand, and the answer is 56.

Upvotes: 4

djechlin
djechlin

Reputation: 60768

You can reduce this to the case for just one path on one grid. Make a second copy of the grid, rotate the second copy, then matrix-add them together and solve on the new grid with just one path. The dynamic programming problem is easy from there (i.e. compute partial maximums for each node).

Upvotes: 1

Related Questions