题目如下：

如下图，某物流派送员p，需要给 a、b、c、d. 4个快递点派送包裹，请问派送员需要选择什么样的路线，才能完成最短路程的派送。假设如图派送员的起点坐标(0,0)，派送路线只能沿着图中的方格边行驶，每个小格都是正方形，且边长为1，如p到d的距离就是4。随机输入n个派送点坐标，求输出最短派送路线值（从起点开始完成n个点派送并回到起始点的距离）。 

输入示例： 
4 
2,2 
2,8 
4,4 
7,2 
输出： 
30

拿到这道题首先要分析题目，要求最短派送的路线，可以遍历出所有路径一一对比，也可以采用回溯算法。

 1 import java.util.Scanner;
 2 
 3 //定义一个坐标类
 4 class Point{
 5     //(x,y)坐标
 6     int x,y;
 7     //判断是否遍历过的标志变量
 8     boolean isVisited;
 9     
10     //构造函数
11     public Point(int x, int y) {
12         this.x = x;
13         this.y = y;
14         this.isVisited = false;//初始化为false，若遍历过则置为true 
15     }
16     
17     //获得该点到指定点的距离
18     public int getLength(Point p) {
19         return Math.abs(x-p.x) + Math.abs(y-p.y);
20     }
21 }
22 
23 //处理最短路径的方法类
24 public class Method{
25     //起始点
26     static Point  StartPoint = new Point(0, 0);
27     //最小路径先设为系统最大值
28     static int minPath = Integer.MAX_VALUE;
29     
30     /**
31      * 定义获取给定点到其余点的最小路径的方法，递归调用
32      * @param point        给定的起始点
33      * @param points    其余的点
34      * @param totalLen    起始点到遍历点的距离和
35      * @param count        用来对遍历过的点计数
36      * @return
37      */
38     public static int caculate(Point p, Point[] points, int totalLen, int count) {
39         //判断停止条件,如果所有的点遍历完，则返回
40         if(points.length==count) {
41             minPath = Math.min(minPath, totalLen + p.getLength(StartPoint));
42             return minPath;
43         }
44         
45         //否则遍历其余的点并进行路径和的计算
46         for(int i=0; i<points.length; i++) {
47             //判断此点是否遍历过
48             if(points[i].isVisited==false) {
49                 //计算起始点到遍历点之间的距离，从而更新最小路径
50                 totalLen += points[i].getLength(p);
51                 
52                 //若小于最小路径，则更遍历此点继续下一步
53                 if(totalLen<minPath) {
54                     //该点的标志位置为true
55                     points[i].isVisited = true;
56                     //每遍历一个点，计数器加1，起始点更改为遍历后的点,继续计算其余点
57                     caculate(points[i], points, totalLen, count+1);
58                 }
59                 //将路径和倒减，标志置为false，进行下一个方案的计算
60                 totalLen -= points[i].getLength(p);;
61                 points[i].isVisited = false;
62             }
63         }
64         return minPath;
65     }
66     
67     public static void main(String[] args) {
68         int totalLen = 0, count = 0;
69         //从键盘获取输入
70         Scanner input = new Scanner(System.in);
71         int num = Integer.parseInt(input.nextLine());
72         int n = num;
73         Point[] points = new Point[n];
74         //获得输入点的坐标并存入坐标数组中
75         for(int i=0; i<points.length; i++) {
76             String[] strings = input.nextLine().trim().split(",");
77             points[i] = new Point(Integer.parseInt(strings[0]), Integer.parseInt(strings[1]));
78         }
79         
80         //计算最优路径并打印到控制台
81         minPath = caculate(StartPoint, points, totalLen, count);
82         System.out.println(minPath);
83     }
84 }
85 
86 /*
87  * 以上代码参考https://blog.csdn.net/s_yj_q/article/details/81132765， 如有错误，各路大神多多指教。
88  */

View Code