Given a 2d grid, at each cell of the grid there is an integer (can be negative as well), we need to start at the top left of the grid and reach the bottom-right cell. On going to each cell our points increase/decrease to the integer contained in that cell. Also there are some cells given (i,j) from which we need to visit at least one. We need to collect maximum points and reach the last cell. How to solve this problem ? Any help would be appreciated.
Problem Source?
1 Like
Encountered this problem in a company’s test
Are we allowed to revisit a cell ?,also can we move in any direction or only to down or right?
1 Like
sorry i forgot to mention we can only move down/right in one move
Dynamic Programming .
2 Likes
yeah i did try with dp. but was confused about how to make sure to visit particular cells at least once.
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
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.
using dynamic programing
could u please elaborate
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
hey its like its not compulsory to visit all of them but u need to visit atleast one of those K cells.
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
Thanks this was simple. Did not strike me during the test.
1 Like
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).
hey actually its not compulsory to walk through all K cells. Its compulsory to visit atleast one of the K cell.
Ohh Sorry ,
My Bad .
Hey I think this question is quite different from the one u shared.
Yeah even I misread the problem twice, check this comment I’ve solved the version you’re talking about in it.
1 Like