Given a matrix of N*M , find the minimum no. steps in worst case to reach to particular cell?

Question

One can enter the matrix from any cell, and each cell contains some clue regarding the position of the cell needed to be found like

Total 8 types of clues can be present:

Exactly Above it
Exactly Below it
Exactly To the Right
Exactly To the Left
In the Top Right Region
In the Bottom Right Region
In the Top Left Region
In the Bottom Left Region

In each step he can move to one adjacent cell as per the above eight movements. My question is minimum no. of steps he needs to take to reach that cell in the worst case.

     Test Case :
     2 2       : 1
     3 3       : 1 

My solution looked like this : I thought If I start from the middle region of the matrix , then I would have to take the minimum no. of steps.

   cin >> n >> m ;
   ans = max ( n/2 , m/2 ) ;

But obviously it was wrong. The correct solution looked like this

   cin >> n >> m ;
   ans = log( max(n,m) , 2) ; //base 2

Can anyone explain this ?

The question can be found here : http://www.codechef.com/TRNT2014/problems/TR001

Answer 1

Contrary to the description above, the linked description does not seem to limit which box you can check at any time.

As such, the correct approach seems to be basically a 2D binary search. Start at the middle box. If (for example) the clue says the correct box is up and to the right, move half the distance toward that corner. At that point, it might say (for example) that the correct box is up and to the left. If so, you move half the distance that direction.

In short, it's a binary search, except that the result at each point is a vector--a direction and a distance--rather than just a distance as you'd have in a typical 1D binary search.

Answer 2

These two items:

In each step he can move to one adjacent cell as per the above eight movements.

The correct solution looked like this:
  ans = log( max(n,m) , 2) ; //base 2

are in contradiction. If the first is true, then your solution is correct. If the second is true, then the first must be false, and he can jump to any cell (or at least a cell (n/4,m/4) away).