How to solve this grid problem

help
2

Problem Source?

1 Like
3

Encountered this problem in a company’s test

4

Are we allowed to revisit a cell ?,also can we move in any direction or only to down or right?

1 Like
5

sorry i forgot to mention we can only move down/right in one move

6

Dynamic Programming .

2 Likes
7

yeah i did try with dp. but was confused about how to make sure to visit particular cells at least once.

8

You can run a DP according to the following recurrence,
DP[i][j] → max score you can get if you start from (i,j) and finish the route at (N,M),so the recurrence would look like,

DP[i][j]=A[i][j]+\max (DP[i+1][j],DP[i][j+1])

Answer would just be DP[0][0]

1 Like
9

This is simple maximum cost path but the condition in my question is that there are several cells whose indexes are given called magical cells among which at least one we necessarily need to visit and keeping this in consideration find the maximum score.

10

using dynamic programing

11

could u please elaborate

12

Okay, I see I misread the question. So what you can do is this,
say there are K such cells which need to be visited at least once we sort them by their
column number
And we will process the cells in order of decreasing column number and restart the DP I mentioned above on each such cell in this way we’ll ensure that we’ll visit all of those K cells.

1 Like
13

hey its like its not compulsory to visit all of them but u need to visit atleast one of those K cells.

14

OKay that’s even simpler, Just run the same dp twice one time with cell (0,0)(say DP_1[i][j]) as the source and second time with cell (N,M) as the source say DP_2[i][j]. Now iterate over all the K special cells and take the max over DP_1[i][j]+DP_2[i][j]-A[i][j]. That would be the answer.

DP_1[i][j] → max weight path to reach cell (i,j) from cell (0,0), and DP_2[i][j] → max weight path to reach cell (N,M) from cell (i,j)

2 Likes
15

Thanks this was simple. Did not strike me during the test.

1 Like
16

U can also solve this using recursion. I can suggest you a video that can be helpful for you.
The given link:(Flood Fill - Solution | Recursion | Data Structures and Algorithms in JAVA - YouTube).

18

hey actually its not compulsory to walk through all K cells. Its compulsory to visit atleast one of the K cell.

19

Ohh Sorry ,
My Bad .

20

Hey I think this question is quite different from the one u shared.

21

Yeah even I misread the problem twice, check this comment I’ve solved the version you’re talking about in it.

1 Like
22

It is very much similar to this CSES problem set in dynamic programming