2018阿里巴巴秋招内推Java研发岗位在线编程测试题

题目：坐标图上有n个点，求要从原点到这n个点各去一次的最短路线长度，只能沿坐标格走，例：从（0,0）到（1,2），要先往x轴方向走一步，再往y轴方向走两步。

样例输入：第一行表示点的个数，其余的行表示各点横纵坐标，用逗号分开。
3
1,2
3,4
5,6
样例输出：先到（1,2），再到（3,4），再到（5,6）的路径最短，输出路径长度。
11

分析：dp问题，求出原点到各点及各点之间相互的距离，不重复的前提下，找出从原点出发其他点各走一次的最短距离。

代码（可能有些地方写得复杂化了）：

import java.util.*;

public class Main {

    static int calculate(Integer[] x,Integer[] y) {
        int num = x.length;
        int[][] dist = new int[num+1][num];
        for(int i = 0;i<num;i++) {//求各点距离
            for(int j = 0;j<num;j++) {
                if(i != 0)
                    dist[i][j] = Math.abs(x[j]-x[i])+Math.abs(y[j]-y[i]);
                else
                    dist[i][j]=Math.abs(x[j])+Math.abs(y[j]);
            }
        }

        int min = dist[0][0];
        for(int i=0;i<num-1;i++)
            min+=dist[i+2][i];

        for(int j=0;j<num;j++) {//求最短距离
            int temp = 0;
            temp+=dist[0][j];
            for(int i1=1;i1<num&&i1!=j;i1++) {
                temp += dist[i1][j];
                for(int i2=1;i2<num&&i2!=j&&i2!=i1;i2++) {
                    temp += dist[i2][i1];
                    for(int i3=1;i3<num&&i3!=j&&i3!=i1&&i3!=i2;i3++) {
                        temp += dist[i3][i2];
                        if(temp<min)
                            min = temp;
                    }
                }
            }
        }

        return min;
    }


    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        String[] locations = new String[num];
        for(int i = 0;i < num;i++) {
            locations[i] = scanner.next();
        }

        Integer[] x= new Integer[num];//转化成坐标
        Integer[] y= new Integer[num];
        for(int i=0;i<num;i++) {
            char c = locations[i].charAt(0);
            String s=String.valueOf(c);
            int k=Integer.parseInt(s);
            x[i] = k;
            c = locations[i].charAt(2);
            s=String.valueOf(c);
            k=Integer.parseInt(s);
            y[i] = k;
        }

        System.out.println(calculate(x,y));  
    }
}