Onesh0t's blog

By Onesh0t, history, 3 years ago, In English

Hey can someone please help.this question was asked in an interview. There are N points on a 2D- grid in the form (x,y). The distance between any two points x1,y1 and x2,y2 is=|x1-x2|+|y1-y2|. We have to traverse all the points starting from any one such that the total distance travelled by you is minimum. But, there are M restrictions, in the form u,v such that you cannot traverse v after covering u.
Eg- input- 5 (N=Number of points) (x,y coordinates of these points) 1,1 2,2 3,3 4,4 5,5 (M=number of restrictions) 2 1 2 (meaning you cannot traverse 2nd point(2,2) after covering 1st(1,1)) 3 4 (meaning you cannot traverse 4th point(4,4) after covering 3rd(3,3)) output-8 explanation--- > traverse in the order (5,5 ------>4,4------>3,3----> 2,2---> 1,1)

Read more »

  • Vote: I like it
  • +22
  • Vote: I do not like it