problem
某物流派送员p，需要给a、b、c、d4个快递点派送包裹，请问派送员需要选择什么的路线，才能完成最短路程的派送。假设如图派送员的起点坐标(0,0)，派送路线只能沿着图中的方格边行驶，每个小格都是正方形，且边长为1，如p到d的距离就是4。随机输入n个派送点坐标，求输出最短派送路线值（从起点开始完成n个点派送并回到起始点的距离）
solution
回溯法解决，全排列遍历所有路径，计算
import java.io.BufferedInputStream;
import java.util.Scanner;
/**
* 回溯
*/
public class Main {
/**
* 最小路径长度
*/
private static int res = Integer.MAX_VALUE;
/**
* 定义点的数据结构
*/
static class Point {
int x;
int y;
boolean visited = false;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
/**
* 计算两点长度
* @param anotherPoint
* @return
*/
public int calcuDis(Point anotherPoint) {
return Math.abs(x - anotherPoint.x) + Math.abs(y - anotherPoint.y);
}
}
public static void main(String[] args) {
Scanner in=new Scanner(new BufferedInputStream(System.in));
int n=in.nextInt();
Point[] points=new Point[n];
for(int i=0;i<n;i++){
String s = in.next() ;
String[] nums = s.split(",") ;
int a = Integer.parseInt(nums[0]) ;
int b = Integer.parseInt(nums[1]) ;
points[i]=new Point(a,b);
}
dfs(points,new Point(0,0),0,0);
System.out.println(res);
}
public static void dfs(Point[] points, Point start, int sum, int count) {
for (int i = 0; i < points.length; i++) {
if(! points[i].visited){
points[i].visited = true;
count++;
sum+=start.calcuDis(points[i]);
if(count==points.length){
sum+=points[i].calcuDis(new Point(0,0));
if(sum<res){
res = sum;
}
}
dfs(points, points[i],sum,count);
points[i].visited = false;
sum-=start.calcuDis(points[i]);
count --;
}
}
}
}