kitchent After finishing Problem 83 with Dijkstra, I came back here to try this problem also with Dijkstra. It is interesting how the difference in the size constraint makes it implausible to construct the graph in advance. Doing so results in Runtime Error in Python for the last 3 test cases, which I suppose is related to the memory-heavy nature of
dictdata type.It is also noticeable that using Dijkstra is not necessarily faster than a naive loop-the-whole-thing-until-nothing-can-be-changed approach.
tieros 2 days struggling and I finally passed all test with Dijkstra's algo, slowest TC at 6.35 secs with Python. After runtime errors I thought about using Dijkstra without creating a dictionary graph (we already know all edges, [i][j]->[i][j+1], ...) and tried to put all solution inside Dijkstra. But after spending hours to fix it I looked for similar implementations on net and found some nice simple ways to do it. (it became 5 times faster than Dijkstra with dict graph but still 4 times slower than DP solution)
ErikTillema Didn't enjoy solving this problem a lot: I was hoping that an optimized version of Dijkstra (advancing column per column, thereby keeping the sorted set small) would work but all my attempts resulted in some time-outs. So it seems that DP O(n^2) is the only way to go. Speaking only for .NET languages that is.
shashikrishna I am getting 2 test cases right. For rest of the cases segmentation faults are coming.
nitishingde don't forget to use unsigned long long int :/
NourSamir this problem is so weird to me i tried to solve it using DP here is my solution idea : func(x,y) : check limits of the grid , if(y = last col) return grid[x][y] , minmize between func(x+1,y), func(x-1,y), func(x,y+1) + grid[x][y] . but this solution crash and goes into infinite recursive calls , hints pleaee
HassanFawaz you should check before each recursive call to not check a cell that already has been checked for example if you are in the middle you will go up then go down then go up then go down infinitly hence the infinite recursive calls
Indrasen the question seems to be unclear.. why didnot you selected 37 in second last column? .. since that is the min value for that column by using the property of going down in the column .
itsmeyunhan Because the destination is the most right column.
No more comments
Sort 9 Discussions, By:
Please Login in order to post a comment