Friday, February 6, 2015

Least moves

Given a m*n grid starting from (1, 1). At any point (x, y
   ), you has two choices for the next move: 1) move to (x+y, y); 2) move to (x, y+x); From point (1, 1), how to move to (m, n) in least moves? (or there's no such a path) 

At first I thought I should use DP, but after taking a look at other people's solutions, I realize it is not that complicated.

If m = n and both m and n are greater than 1, then there is no solution. This is because at any time we will move to x+ y, y or x, y + x then there are only two possibilities for the last move:

x + y = m
y = n

or
x = m
y + x = n

if m = n, either of these will lead to x = 0 or y = 0, which is impossible since the start point is (1, 1), thus at anytime when m = n and m > 1, there is no solution.

Then the next thing is to start from m and n, goes back to 1, 1.


public static int leastMoves(int m, int n) {
  if (m == n && m == 1)
   return 0;
  if (m == n && m > 1)
   return -1;
  int count = 0;
  while (m > 1 || n > 1) {
   if (m == n)
    return -1;
   else if (m > n) {
    m -= n;
    count++;
   }
   else {
    n -= m;
    count++;
   }
  }
  if (m != 1 || n != 1)
   return -1;
  return count;
 }

No comments:

Post a Comment