And when one doesn't do it right, one will just end-up visiting each cell anyway.

That would have no benefit over this bottom-up approach.

> And when one doesn't do it right, one will just end-up visiting each cell anyway.

And I think there is no algorithm which can guaranty otherwise.

consider this input

     2
    2 2
   2 2 2
  2 2 2 2    
 . . . . .       2s in between
2 2 . . 2 1      last row
[download]

no matter which top-down search you apply, you can move the 1 in a way that it's only found at last try.

Which means all cells needed to be visited.°

update

°) NB: complexity big O() calculations are about worst case (if not stated otherwise )

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}