18年阿里校园秋招笔试（送快递）

忘是亡心i 2022-05-14 02:50 220阅读 0赞

题目如下：

![70][]

**思路：**深度优先搜索+回溯

**注意事项：**最终要回到起点

首先是定义一个“坐标点”类

属性包含：x坐标y坐标

该点是否被经过的标记

方法包含：计算距离

package Alibaba.Transport;
    
    public class Point {
    
    	int x;
    	int y;
    	boolean isVisited;
    
    	// public Point(){}
    	public Point(int x, int y) {
    		this.x = x;
    		this.y = y;
    		this.isVisited = false;
    	}
    
    	public int getDistance(Point p) {
    		return Math.abs(this.x - p.x) + Math.abs(this.y - p.y);
    	}
    
    	@Override
    	public String toString() {
    		return "[x=" + x + ", y=" + y + ", isVisited=" + isVisited + "]";
    	}
    	
    }

下面是主类

package Alibaba.Transport;
    
    import java.util.Scanner;
    
    /**
     * 货车送快递:
     * 输入:	n个领取点
     * 		各领取点的坐标
     * 		计算经过每个点配送的最短总距离
     * 输出:总距离
     * 注意:最后回到出发点
     */
    public class Main {
    	static int minpath = Integer.MAX_VALUE;
    	static final Point _start = new Point(0,0);			// 声明起点坐标
    	
    	public static void main(String[] args){
    		Scanner sc =new Scanner(System.in);
    		String pureStr = sc.next().trim();		// 删除任何前导和尾部空格
    		int num = Integer.parseInt(pureStr);	// 存入配送点的数量
    		
    		Point[] points = new Point[num];		// 声明含有num个点的Point[]数组
    		
    		for(int i = 0; i<num; i++){
    			String[] coordinate = sc.next().trim().split(",");
    			int codinX = Integer.parseInt(coordinate[0]);
    			int codinY = Integer.parseInt(coordinate[1]);
    			points[i] = new Point(codinX,codinY);		// 取到x,y值放入点
    //			System.out.println(points[i]);
    		}
    		calDistans(_start,points,0,0);
    		System.out.println(minpath);
    	}
    	
    	public static void calDistans(Point start, Point[] points, int sum, int count){
    		if(count == points.length){
    			sum += start.getDistance(_start);	// 回到起点
    			if(sum<minpath){
    				minpath = sum;
    			}
    			return;
    		}
    		
    		for(int i = 0; i<points.length; i++){
    			if(!points[i].isVisited){
    				points[i].isVisited = true;
    				calDistans(points[i], points, sum + start.getDistance(points[i]),count+1);
    				points[i].isVisited = false;	// 下一个点之前,将访问置为false
    			}
    		}
    	}
    
    }

[70]: /images/20220514/c6e9730c029c4ab8a58bc0964fa025c8.png