Netease written test No. 2 -- typical application of European distance

Preface

      Euclid measures （euclidean metric）（ Also known as Euclidean distance ） Is a commonly used definition of distance , Referring to m The real distance between two points in dimensional space , Or the natural length of the vector （ That is, the distance from this point to the origin ）. Euclidean distance in two-dimensional and three-dimensional space is the actual distance between two points .

       The formula of two-dimensional space

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

       The formula of three-dimensional space

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

       Their thinking : European distance cannot be 2, top left corner (4*4) Satisfy , In the upper right corner, you can see in the same line a[i][j-2] Is there a cake , If it does not exist , Then put the cake . If the lower left corner is in the same column , Then look at a[i-2][j] Is there a cake , If it does not exist , Then put the cake . For the lower right corner , Then look at a[i-2][j]、a[i][j-2] Is there a cake , If it does not exist , Then put the cake .

package cn.edu.ujn.nk; import java.util.Scanner;import java.util.regex.Pattern; /** * 2016-08-09 --01 *  No two  *  Er Huo Xiaoyi has one W*H Grid box , The row number of the grid is 0~H-1, The column number of the grid is 0~W-1. At most one cake can be placed in each grid , The Euclidean distance between any two cakes cannot be equal to 2. *  For two lattice coordinates (x1,y1),(x2,y2) Euclidean distance of : ( (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2) ) The arithmetic square root of  *  Xiao Yi wants to know how many cakes can be put in the grid box at most . *  Input description :  Each array contains the length and width of the grid W,H, Split with spaces .(1 ≤ W、H ≤ 1000) * *  Output description :  Output a maximum number of cakes  * *  Input example : 3 2 * *  Output example : 4 * * @author SHQ * */public class NotTwo { /** * @param args */public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextLine()) {String str = in.nextLine();if (str.length() == 0) {break;}Pattern pattern = Pattern.compile("[ ]+");String[] arr = pattern.split(str);int w = Integer.parseInt(arr[0]);int h = Integer.parseInt(arr[1]); System.out.println(notTwoGreed(h, w));} } private static int notTwo(int h, int w) {int cnt = 0;for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {if ((i / 2 + j / 2) % 2 == 0)cnt++;}}return cnt;}private static int notTwoGreed(int h, int w) {int [][] a = new int [h][w];int cnt = 0;for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {//  Top left if(i< 2 && j < 2){a[i][j] = 1;cnt++;//  The upper right }else if(i < 2 && j-2 >= 0 && a[i][j-2] != 1){a[i][j] = 1;cnt++;//  The lower left }else if(j < 2 && i - 2 >= 0 && a[i-2][j] != 1){a[i][j] = 1;cnt++;//  The lower right }else if(i >= 2 && j >= 2 && a[i-2][j] != 1 && a[i][j-2] != 1){a[i][j] = 1;cnt++;}}}return cnt;}}

​