Islands Travel 微软2016校园招聘笔试题

<pre name="code" class="java">import java.util.*;
public class IslandsTravel1138 {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNext()) {int n=in.nextInt();int[][] a=new int[n][2];for(int i=0;i<n;i++){a[i][0]=in.nextInt();a[i][1]=in.nextInt();}int[][] map=new int[n][n];for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){map[i][j]=Math.min(Math.abs(a[i][0]-a[j][0]), Math.abs(a[i][1]-a[j][1]));}}List<Integer> list1=new ArrayList<Integer>();List<Integer> list2=new ArrayList<Integer>();int min=Integer.MAX_VALUE;int x=0;int y=0;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(map[i][j]<min){min=map[i][j];x=i;y=j;}}}list1.add(x);list1.add(y);int sum=0;sum+=map[x][y];for(int i=0;i<n;i++){if((i!=x)&&(i!=y)) list2.add(i);}while(list1.size()<n){int[] tmp=new int[2];int tmpmin=Integer.MAX_VALUE;for(int i=0;i<list1.size();i++){for(int j=0;j<list2.size();j++){int xx=list1.get(i);int yy=list2.get(j);if(map[xx][yy]!=0&&map[xx][yy]<tmpmin){tmpmin=map[xx][yy];tmp[0]=xx;tmp[1]=yy;}}}sum+=tmpmin;list1.add(tmp[1]);list2.remove(Integer.valueOf(tmp[1]));}System.out.println(sum);}}
}

2. dijkstra算法

<pre name="code" class="java">import java.util.Scanner;
import java.util.*;
public class IslandsTravel2 {public static void main(String[] args) {int MAX=Integer.MAX_VALUE;Scanner in = new Scanner(System.in);int n=in.nextInt();int[][] a=new int[n][2];for(int i=0;i<n;i++){a[i][0]=in.nextInt();a[i][1]=in.nextInt();}int[] dis=new int[n];boolean[] flag=new boolean[n];flag[0]=true;for(int i=1;i<n;i++){dis[i]=getdis(0,i,a);}for(int i=1;i<n;i++){int index=-1;int min=MAX;for(int j=1;j<n;j++){if((!flag[j])&&(dis[j]<min)){index=j;min=dis[j];}}if(index==-1) break;flag[index]=true;for(int k=1;k<n;k++){int disjk=getdis(index,k,a);if(disjk+dis[index]<dis[k]){dis[k]=disjk+dis[index];}}}System.out.println(dis[n-1]);}public static int getdis(int i,int j,int[][] a){return Math.min(Math.abs(a[i][0]-a[j][0]), Math.abs(a[i][1]-a[j][1]));}
}

在本题中，最近距离的处理上，还有另一个很重要的性质：

对于任意一个点i，在x坐标和y坐标排序后，坐标值不等于点i，且最靠近点i的点。我们称为点i的邻居。如下图中所示的绿色点：

通过该图可以知道，邻居节点一定是在虚线的交点处，因此对于点i，邻居节点至多有4个。并且在图中黄色的区域，也就是点i的上下左右4个区域内是不存在其他点的。其他点只能存在于绿色的区域内。

假设有一个点j，存在于绿色区域内，可以证明从点j直接到点i的距离一定不会优于点j先到邻居节点再到点i。

通过邻居节点则：

由于：

因此有：

所以我们并不需要将点i和点j的边进行连接，只需要连接点i和邻居节点的边即可。

<pre name="code" class="java">import java.util.Scanner;
import java.util.*;
public class IslandsTravel3SPFA {final static int MAXINT = 1000000000;public static void main(String[] args) {int MAX=Integer.MAX_VALUE;Scanner in = new Scanner(System.in);while(in.hasNext()){int n=in.nextInt();Node[] node=new Node[n];for(int i=0;i<n;i++){node[i]=new Node(in.nextInt(),in.nextInt(),i);}List<List<Dis>> graph=new ArrayList<List<Dis>>();for(int i=0;i<n;i++){graph.add(new ArrayList<Dis>());}build(node,graph);for(int i=0;i<n;i++){swap(node[i]);}build(node,graph);int[] dis=new int[n];for(int i=1;i<n;i++){dis[i]=MAX;}LinkedList<Integer> queue=new LinkedList<Integer>();queue.add(0);//设置queue标志位，避免计算是否包含浪费时间boolean[] flag=new boolean[n];flag[0]=true;while(!queue.isEmpty()){int k=queue.pollFirst();List<Dis> list=graph.get(k);flag[k]=false;for(Dis tmp:list){int num=tmp.num;int d=tmp.d;if(dis[k]+d<dis[num]){dis[num]=dis[k]+d;if(flag[num]==false){queue.add(num);flag[num]=true;}}}}System.out.println(dis[n-1]);}in.close();}public static void build(Node[] A,List<List<Dis>> graph){Arrays.sort(A);int n=A.length;for(int i=1;i<n;i++){int num=A[i].num;int pre=A[i-1].num;graph.get(num).add(new Dis(pre,A[i].x-A[i-1].x));graph.get(pre).add(new Dis(num,A[i].x-A[i-1].x));}}public static void swap(Node node){int tmp=node.x;node.x=node.y;node.y=tmp;}public static class Node implements Comparable<Node>{int x;int y;int num;Node(int x,int y,int num){this.x=x;this.y=y;this.num=num;}@Overridepublic int compareTo(Node node) {// TODO Auto-generated method stubif(this.x>node.x) return 1;else if(this.x<node.x) return -1;else return 0;}}public static class Dis{int num;int d;Dis(int num,int d){this.num=num;this.d=d;}}}