Hi All,
Please help in this interesting grid problem.
There is a grid of dimension N * M (1 <= N,M <=500). Each cell contains a number K (0 <= K <= 10^5). Currently we are at cell (1,1) and we need to go to cell (N,M).We pick each number that is present in the current cell as we proceed along the path. Transitions are as follows: From position (r,c) we can go to (r+1,c) or (r,c+1) or (r+1,c+1).
We need to print the cell positions of lexicographical largest path among all possible paths. example :
1 2 3
4 5 6
7 8 9
In above matrix path [(1,1),(2,2),(3,3)] is largest.
Thanks in advance ...
Auto comment: topic has been updated by ritesh_tiwary (previous revision, new revision, compare).
Auto comment: topic has been updated by ritesh_tiwary (previous revision, new revision, compare).
Can you post a link to the problem
Actually the problem was asked in hack a Heart tie breaker round on hackerearth, Which can't be accessed now.
Always greedily choose to take the largest next value you can.
The problem is, if there are several cells with that value, you can't know which one to choose. So just take all of them. What I mean is, keep a set of cells S that are currently maximal, and in each iteration consider all the cells that you can reach from any cell in S, and replace S with this new set. Also remember, for each cell, where you first reached it from, so you can reconstruct the answer later: when you finally reach (N,M), just print the entire reconstruction from (N,M) to (1,1).
Got it,Thanks a lot.
I stuck at this problem for a long time.Thank you.