Mar 31, 2008

Find minimum steps required

Given a 2-d space with origin (0,0); find in how many minimum steps can a knight reach to a point (x,y) from (0,0)? Is it possible to traverse to any such point in the space from (0,0) or we have some specific conditions on x, y for such a path to exist? Prove your arguments.

Would your algorithm be still valid if traversing in x-axis direction is cheaper than traversing in y-axis direction or vice versa?

PS: a knight walks 2 units in X-axis and 1 unit in Y-axis or 2 units in Y-axis and 1 unit in X-axis in one move.

No comments: