>From (a,b) to (c,n) => What about traversing all columns n >= j >= a as we can move up-down-right anytime we want.
On Dec 14, 5:57 pm, Azhar Hussain <[email protected]> wrote: > We need not necessarily pick the apple. We need to suggest a way that could > have maximum apples and path need not be longest. Another person will > follow our path and pick the apples. > > we can start from specified (i,j) and have to reach specified (i, n) > traversing either top, right, down(not left). Can greedy approach work if > we take a graph and try to implement shortest path algorithm(in this case > max apples) from (i, j) to (i,n)? > > - > Azhar. > > > > > > > > On Wed, Dec 14, 2011 at 6:07 PM, Gene <[email protected]> wrote: > > Longest path won't work so well because it will return infinity if a > > path contains a positive cycle, which doesn't apply here because once > > you pick up an apple, it's gone. > > > On Dec 13, 7:17 am, vikas <[email protected]> wrote: > > > Graph > > > take up, right and bottom as nodes connected to current and do find > > > max path. > > > > On Dec 13, 3:44 pm, Azhar Hussain <[email protected]> wrote: > > > > > We have apples arranged in a mxn matrix. We start from the upper left > > > > corner and have to reach bottom right corner with maximum apples. We > > can > > > > only move either down or right. > > > > Now if we can start any where in the matrix and have to reach > > anywhere on > > > > the right(reach n column). We can either up, down, right(but not > > left). We > > > > have to collect maximum apples from a given location. > > > > I am trying to solve problem. solution for the first one is given > > athttp://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg. > > > > What data structure would be suitable for the second problem and will > > > > dynamic programming work. > > > > > Thanks in advance. > > > > Azhar. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
