I hope it's obvious now that this makes it pretty much
O(n**2)
with
n = length = #rows= #columns
because the number of optimal solutions is "bigger" than eternity.
Counting the distance of slides makes this far more complicated, such that you should change the challenge to "best solution so far" instead of "optimal solution".
It's also important to understand that optimal sum is easy, shortest (Hamilton) path is problematic.
My approach would be a two dimensional divide and conquer.
Like for n=1024=2**10 solving 32 smaller grids with n=32=2**5 side length.
One could also divide further to 5 stages since 4**5=1024.
The basic idea is still probabilistic.
Because of your randomization there is a probability of roughly .5 that a cell is positive.
Hence two neighboring cells (minimal distance) have the probability of .25 to be both positive.
This means that if you need to find a minimal transit between two areas with m neighboring cells, then the there is a 1-0.75**m to find it.
Hence finding very good solutions is not that difficult.
It's the optimal solution which is on another page.
But in terms of a coding challenge this should be a big plus, because the crowd loves rankings and hates math. ;)
Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery
In reply to Re^3: Code challenge: Route planning on a 2D grid
by LanX
in thread Code challenge: Route planning on a 2D grid
by bliako
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |