|
|
back to boardDiscussion of Problem 1325. DirtHow to solve this problem?I used Djkstra,but I've got TLE. Re: How to solve this problem?I used Djkstra,but I've got TLE. Lee algorithm. Runs in O(N * M). If you don't know it, here is a short description: you start from starting position (sl, sc) and now you expand this node; in a queue you put all its neighbours. You do this only if you optimize by going to that neighbour, i.e. the current cost is shorter than the previous one. let a[i][j] be a matrix with two fields: boots and length. a[i][j] means: minimum number of boots and minimum length to reach (i, j) from start position. You expand from (x, y) to a neighbour (c, d) when: a[x][y].boots + 1 (if you change boots, 0 else) < a[c][d].boots or a[x][y].boots + 1 = a[c][d].boots and a[x][y].length + 1 < a[c][d].length. Obvious, you take the valid neighbours (not 0s or outside ones) hope it's clear... Why do you think it works only O(N*M)? I used Dijkstra with K-based Heap and got AC It could be proved that in Dijkstra's algorithm the choice K = E /V is assimptotically optimal. So, applying to our problem, E / V equals to 8. Re: How to solve this problem?I used Djkstra,but I've got TLE. Posted by Melody 19 Apr 2004 20:55 I just used the algorithm as you described. But it got tle. Anyway thank you very much. Now I've got it,using heap will help me. Edited by author 19.04.2004 20:55 Re: Lee's algorithm I wrote the solution with Lee's algorithm, as it was discribed above by Gheorghe Stefan, and got TL on test 16. I doubt it works in O(MN). I test the solution at my local computer - it gaves the correct answers (obviously), but works about 10 times slower, then my solution with Dijkstra! Re: Lee's algorithm I BFS on number of boots and Dijkstra on walk-length inside odd/even slices. Dijkstra is linear-time here because of same-length edges (front line is kept as bidirectional list in non-descending order of walk-length, insertion position goes only forwards). AC in 0.062 sec :) Edited by author 21.08.2008 21:13 Re: Why do you think it works only O(N*M)? Posted by Sq1 16 Aug 2017 01:32 Can someone explain where is the problem in this solution? |
|
|