CODEWITHSUNDEEP
calgorithmmatrixroutesdynamic-programming
2147483647
2147483647

Reputation: 1197

How do we find two most-weighted routes in a grid?

We a given a weighted N*N grid W. Two robots r1,r2 start from top left and top right corners respectively. R1 has to reach to the bottom right and R2 the bottom left corners. Here are the valid moves.

  • R1 moves one square down, R2 moves one square left.
  • R1 moves one square right, R2 moves one square down.

They must move in such a way that the sum of the weights of the squares they visit (including the starting and ending square) is maximized.

For Examples, if the grid is:

6   0   3   1
7   4   2   4
3   3   2   8
13  10  1   4

In this example, if R1 follows the path marked by * and R2 follows the path marked by ^, as shown below, their combined score is 56.

 6*   0     3^   -1^
 7*   4*^   2^    4
-3    3*^  -2*    8*
 13^  10^  -1    -4*

It can be verifyed that this is the best combined score that can be achieved for this grid.

We cannot solve this by recursion as N <= 2500 and the time limit is 2 seconds.
If the problem had only one robot, we could solve this by using dynamic programming.

I tried using a similar approach for this problem;

We have two extra N*N grids G1,G2,

for i from 1 to N:
   for j from 1 to N and K from N down to 1:  
     if (G1[i-1][j] + G2[i][k+1]) > (G1[i][j-1] + G2[i-1][k]):
        G1[i][j] = G1[i-1][j] + W[i][j]
        G2[i][k] = G2[i][k+1] + W[i][k]
     else:
        G1[i][j] = G1[i][j-1] + W[i][j]
        G2[i][k] = G2[i-1][k] + W[i][k]

return G1[N][N] + G2[N][1]

but this gives a wrong answer. I am not able to understand what is wrong with my algorithm, because for each square it is calculating the max weighted path to rech there.

Can anyone tell me what is wrong with my method and how can i correct it to get the correct answer?

Upvotes: 2

Views: 388

Answers (2)

amit
amit

Reputation: 178441

It is a graph problem, and the graph is G=(V,E) where:

  • V = Squares x Squares (The Cartesian product of all the squares)
    (You might want to exclude points where (x1,y1)=(x2,y2), it can be easily done).
  • E = { all possible ways to move in a turn } = (or formally) =
    { (((x1,y1),(x2,y2)),((x1-1,y1),(x1,y1-1))), (((x1,y1),(x2,y2)),((x1,y1-1),(x1-1,y1))) | per x1,y1,x2,y2 }

Now, once we have the graph - we can see it is actually a DAG - and this is a good thing, because for a general case graph - the longest path problem is NP-Hard, but not for DAG.

Now, given a DAG G, we want to find the longest path from ((0,0),(n,n)) to ((n,n),(0,0)), and it can be done with the following approach:

For simplicity define weight((x1,y1),(x2,y2)) = weight(x1,y1) + weight(x2,y2):

The algorithm:

  1. Use topological sort on the graph
  2. Init D((n,n),(0,0)) = weight((n,n),(0,0)) (the target node)
  3. Iterate the graph according to the sort descending and do for each vertex v:
    D(v) = max { D(u) | for each (v,u) in E as described above } + weight(v)

When you are done D((0,0),(n,n)) will have the optimal result.

Upvotes: 1

MajorBlackViking
MajorBlackViking

Reputation: 100

I could see a typo in the 2nd valid scenario

The valid 2nd scenario should be

R1 moves one square right, R2 moves one square down

but was given as

R2 moves one square right, R2 moves one square down

Upvotes: 1

Related Questions