Re^5: Brute force vs algorithm (PWC # 100)

> 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.°

°) 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}

Comment on Re^5: Brute force vs algorithm (PWC # 100) Download Code