@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 <atul.87fri...@gmail.com>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 <hmonfa...@gmail.com>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 <atul.87fri...@gmail.com>wrote: >>> >>>> this recurrence wont work..ignore >>>> >>>> On Mon, Jun 4, 2012 at 8:55 AM, atul anand <atul.87fri...@gmail.com>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 <ankurseth...@gmail.com>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. >>>>>> To post to this group, send email to algogeeks@googlegroups.com. >>>>>> To unsubscribe from this group, send email to >>>>>> algogeeks+unsubscr...@googlegroups.com. >>>>>> 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 algogeeks@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com. >>>> 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 algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> 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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/l9UCuzmoZRMJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
