Save Xiaoyi from Netease written test -- a typical application of Manhattan distance

Preface      

       First, let's introduce Manhattan , Manhattan is a very prosperous neighborhood , skyscrapers , The streets crisscross , from A The location arrives at B The location has no straight path , We have to make a detour , And at least through C place , go AC and CB To get to , Because the streets are very regular ,ACB Like a right angle 3 Horn shape ,AB It's a hypotenuse ,AC and CB It's a right angle side , According to Pythagoras ( Pythagorean ) Theorem , Or vector theory , Can know to use AC and CB Can express AB The length of .

       In early computer graphics , The screen is made up of pixels , Is an integer , The coordinates of points are also generally integers , The reason is that floating point operations are expensive , It's very slow and it's a little bit of an error , If used directly AB Distance of , You have to do floating-point operations , If you use AC and CB, Then just calculate the addition and subtraction method , This greatly improves the speed of computation , And no matter how many times it's accumulated , There will be no error . therefore , Computer graphics borrows Manhattan to name this representation .

       Manhattan distance ： The distance between the two points in the north-south direction plus the distance in the east-west direction , namely d（i,j）=|xi-xj|+|yi-yj|. For one with a due south due north 、 It is a regular Town Street in the direction of East and West , The distance from one point to another is the distance traveled in the north-south direction plus the distance traveled in the east-west direction .

By analyzing the following topics , It is known that Manhattan distance can be used to calculate to (1,1) Point the nearest point , The result value can be calculated according to Manhattan distance . If you don't understand the definition and application of Manhattan , Observe by drawing , In fact, you can also get the answer . Obviously, if you had understood the definition and application of Manhattan distance before , The problem is easy to catch ！

      The code is as follows :

package cn.edu.ujn.nk; import java.lang.reflect.Array;import java.util.ArrayList;import java.util.Scanner;import java.util.regex.Pattern; public class SaveXiaoYi { /** * 2016-08-09 --02 *  There is a piece to save Xiaoyi 1000*1000 Grass of , Xiaoyi initially stood (1,1)( The position of the top left corner ). Xiaoyi will move horizontally or vertically to the adjacent grassland to eat grass every second ( Xiaoyi won't go out of the border ). The villain wants to catch the cute Xiaoyi , He has n Trap . The first i Traps are placed on the abscissa xi , Ordinate for yi  Location , Once Xiaoyi goes into a trap , Will be super captured . In order to save Xiao Yi , You need to know how many seconds at least Xiaoyi may fall into a trap , So as to save Xiao Yi in advance . Input description : The first line is an integer n(n ≤ 1000), It means that Chaochao owns n Trap . The second line has n It's an integer xi, It means the first one i The abscissa of the trap has n It's an integer yi, It means the first one i The vertical coordinates of the traps ensure that the coordinates are within the range of the grassland . Output description : Output an integer , It means that Xiaoyi may fall into the trap of super super in at least how many seconds :34 6 81 2 1 Output example :3 Ideas :  Calculate the shortest distance  */public static void main(String[] args) {Scanner in = new Scanner(System.in);while(in.hasNextLine()){String n = in.nextLine();String x = in.nextLine();String y = in.nextLine();String [] str;int num = 0;ArrayList<Integer> listX = new ArrayList<Integer>();ArrayList<Integer> listY = new ArrayList<Integer>();Pattern pattern = Pattern.compile("[ ]");str = pattern.split(n);num = Integer.parseInt((str[0]));str = pattern.split(x);listX = split(str);str = pattern.split(y);listY = split(str);//int min = listX.get(0) + listY.get(0) - 2;int min = (listX.get(0)-1)*(listX.get(0)-1) + (listY.get(0)-1) * (listY.get(0)-1);int value = 0;int pos = 0, posX, posY;//  Look for the latest trap for(int i = 1; i < num; i++){value = (listX.get(i)-1)*(listX.get(i)-1) + (listY.get(i)-1) * (listY.get(i)-1);//value = listX.get(i) + listY.get(i) - 2; if(min > value){ min = value; pos = i; }}posX = listX.get(pos);posY = listY.get(pos);System.out.println(posX + ":" + posY);int space = (posY - 1) + (posX - 1);System.out.println(space);}}private static ArrayList<Integer> split(String [] str){int len = str.length;ArrayList<Integer> list = new ArrayList<Integer>();for(int i = 0; i < len; i++){list.add(i, Integer.parseInt(str[i]));}return list;}}

notes

      The distance between Manhattan and Euclid ： red 、 The blue and yellow lines indicate that all Manhattan distances have the same length （12）, The green line indicates that Euclidean distance is 6×√2 ≈ 8.48 The length of .

Euclid ( European style for short ) Range of application ：m The real distance between two points in dimensional space . Its calculation formula is as follows :

       The formula of two-dimensional space

      0ρ = sqrt( (x1-x2)^2+(y1-y2)^2 )

       The formula of three-dimensional space

      0ρ = √( (x1-x2)^2+(y1-y2)^2+(z1-z2)^2 )