Timeline for Shortest path in a grid between two points
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 15, 2018 at 9:34 | answer | added | Toby Speight | timeline score: 2 | |
| May 3, 2014 at 21:24 | history | edited | Jamal | CC BY-SA 3.0 |
deleted 22 characters in body; edited title
|
| Jan 5, 2013 at 4:47 | history | tweeted | twitter.com/#!/StackCodeReview/status/287420047591342081 | ||
| Jan 5, 2013 at 1:57 | comment | added | Corbin | Do you happen to have a sample of one of the slow cases? There's a few optimizations that jump out at me, and I'm curious to test them. | |
| Jan 4, 2013 at 19:07 | answer | added | abuzittin gillifirca | timeline score: 0 | |
| Jan 4, 2013 at 18:13 | comment | added | Olavi Mustanoja | 1000x1000 is the upper bound | |
| Jan 4, 2013 at 17:29 | comment | added | abuzittin gillifirca | If this is a programming contest question, which it sounds like, what are the upper bounds for N and M? For a 100000 X 100000 grid of all 1s will take a lot of time with a naive solution. | |
| Jan 4, 2013 at 17:19 | answer | added | Useless | timeline score: 4 | |
| Jan 4, 2013 at 16:53 | answer | added | AndyClaw | timeline score: 5 | |
| Jan 4, 2013 at 16:41 | comment | added | Olivier Dulac | in your case example, it is easy to see there are only 2 routes. On a much bigger case, it could grow quite a lot, but still: on an X/Y tile, you can only progress toward the bottom right at least 1 step (right, or down) : you can't have more than (max(heigth,width)) steps overall in your final solution. If (worst case) all solutinos are at least that long (ex: all tiles contain "1"), it's trivial to compute the worst possible number of steps your algorithm will have to test to cover all possibilities | |
| Jan 4, 2013 at 16:37 | comment | added | Olivier Dulac | tricky part in my solution is to keep track of progress, to explore it all. Recursivity should help (beware you have separate current strings for each path) | |
| Jan 4, 2013 at 16:34 | comment | added | Olivier Dulac | always right or down, always the total amount the case value is at? so it should be very fast : on each step, try both directions: try_right (goes N right, and also store "R" in the current result string), and try_down (goes N down, and stores "D" in the result string). And if you reach exatcly the bottom-right end: keep_result (keeps the current result_string if it is shorter than the previously stored). Otherwise (we go > down or >right than bottom left?) discard current result. | |
| Jan 4, 2013 at 15:27 | history | asked | Olavi Mustanoja | CC BY-SA 3.0 |