Sunday 17 July 2016

Min Steps in Infinite Grid

You are in an infinite 2D grid where you can move in any of the 8 directions :
 (x,y) to 
    (x+1, y), 
    (x - 1, y), 
    (x, y+1), 
    (x, y-1), 
    (x-1, y-1), 
    (x+1,y+1), 
    (x-1,y+1), 
    (x+1,y-1) 
You are given a sequence of points and the order in which you need to cover the points. Give the minimum number of steps in which you can achieve it. You start from the first point.

 /**  
  * @input X : Integer array corresponding to the X co-ordinate  
  * @input n1 : Integer array's ( X ) length  
  * @input Y : Integer array corresponding to the Y co-ordinate  
  * @input n2 : Integer array's ( Y ) length  
  *  
  * Points are represented by (X[i], Y[i])  
  *  
  * @Output Integer  
  *  
  */  
 int coverPoints(int* X, int n1, int* Y, int n2) {  
   int curX = X[0], curY = Y[0];  
   int total = 0, i, j, k;  
   for(i = 1; i < n1; i++){  
     j = abs(X[i] - curX);  
     k = abs(Y[i] - curY);  
     curX = X[i];  
     curY = Y[i];  
     if(j >= k){  
       total = total + j;  
     }else{  
       total = total + k;  
     }  
   }  
   return total;  
 }  
Share:

0 comments:

Post a Comment

Contact Me

Name

Email *

Message *

Popular Posts

Blog Archive