http://www.geeksforgeeks.org/archives/14943
On Mon, Jun 4, 2012 at 7:57 PM, Decipher <[email protected]> wrote: > @Victor - Someone had asked this question from me !! He told me its from > Project Euler Q-83. > @Hassan - I think you are right. This question can be solved by > Dijikstra's algo, if we consider the matrix elements as weights. > > > On Monday, 4 June 2012 16:28:31 UTC+5:30, Hassan Monfared wrote: >> >> moving must be done in A* style >> >> On Mon, Jun 4, 2012 at 1:17 PM, atul anand <[email protected]>wrote: >> >>> i dont think so dijistra will worh here..bcozz we cannot move diagonally >>> ...but according to matrix this path can be considered. >>> >>> On Mon, Jun 4, 2012 at 1:39 PM, Hassan Monfared <[email protected]>wrote: >>> >>>> for non-negative values Dijkstra will solve the problem in ( O(N^2) ) >>>> and Floyd-Warshal is the solution for negative cells. ( O(N^3) ) >>>> >>>> >>>> >>>> On Mon, Jun 4, 2012 at 11:20 AM, atul anand <[email protected]>wrote: >>>> >>>>> this recurrence wont work..ignore >>>>> >>>>> On Mon, Jun 4, 2012 at 8:55 AM, atul anand <[email protected]>wrote: >>>>> >>>>>> find cumulative sum row[0] >>>>>> find cumulative sum of col[0] >>>>>> >>>>>> after this following recurrence will solve the problem. >>>>>> >>>>>> start from mat[1][1] >>>>>> >>>>>> mat[i][j]=mat[i][j]+min( mat[i][j-1] , mat[i-1][j] ) >>>>>> >>>>>> >>>>>> On Sun, Jun 3, 2012 at 7:30 PM, Decipher <[email protected]>wrote: >>>>>> >>>>>>> Q) In the 5 by 5 matrix below, the minimal path sum from the top >>>>>>> left to the bottom right, by moving left, right, up, and down, is >>>>>>> indicated >>>>>>> in bold red and is equal to 2297. >>>>>>> >>>>>>> >>>>>>> *131* >>>>>>> >>>>>>> 673 >>>>>>> >>>>>>> *234* >>>>>>> >>>>>>> *103* >>>>>>> >>>>>>> *18* >>>>>>> >>>>>>> *201* >>>>>>> >>>>>>> *96* >>>>>>> >>>>>>> *342* >>>>>>> >>>>>>> 965 >>>>>>> >>>>>>> *150* >>>>>>> >>>>>>> 630 >>>>>>> >>>>>>> 803 >>>>>>> >>>>>>> 746 >>>>>>> >>>>>>> *422* >>>>>>> >>>>>>> *111* >>>>>>> >>>>>>> 537 >>>>>>> >>>>>>> 699 >>>>>>> >>>>>>> 497 >>>>>>> >>>>>>> *121* >>>>>>> >>>>>>> 956 >>>>>>> >>>>>>> 805 >>>>>>> >>>>>>> 732 >>>>>>> >>>>>>> 524 >>>>>>> >>>>>>> *37* >>>>>>> >>>>>>> *331* >>>>>>> >>>>>>> >>>>>>> >>>>>>> Write an algorithm to find the same. Also, write an algorithm if the >>>>>>> same matrix contains negative numbers (maybe negative cycle) and compare >>>>>>> the space and time complexity of both. >>>>>>> >>>>>>> -- >>>>>>> You received this message because you are subscribed to the Google >>>>>>> Groups "Algorithm Geeks" group. >>>>>>> To view this discussion on the web visit >>>>>>> https://groups.google.com/d/**msg/algogeeks/-/3JeyGNqWbs8J<https://groups.google.com/d/msg/algogeeks/-/3JeyGNqWbs8J> >>>>>>> . >>>>>>> To post to this group, send email to [email protected]. >>>>>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@ >>>>>>> **googlegroups.com <algogeeks%[email protected]>. >>>>>>> For more options, visit this group at http://groups.google.com/** >>>>>>> group/algogeeks?hl=en<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 algogeeks+unsubscribe@** >>>>> googlegroups.com <algogeeks%[email protected]>. >>>>> For more options, visit this group at http://groups.google.com/** >>>>> group/algogeeks?hl=en <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 algogeeks+unsubscribe@** >>>> googlegroups.com <algogeeks%[email protected]>. >>>> For more options, visit this group at http://groups.google.com/** >>>> group/algogeeks?hl=en <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 algogeeks+unsubscribe@** >>> googlegroups.com <algogeeks%[email protected]>. >>> For more options, visit this group at http://groups.google.com/** >>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>. >>> >> >> -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/l9UCuzmoZRMJ. > > 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.
