欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

阿里内推——图的深度搜索

程序员文章站 2022-04-20 22:17:29
...

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

阿里内推——图的深度搜索

注意点

  1. 最后要回到原点
  2. 图的深度遍历

直接上代码

import java.util.Scanner;

/**
 * Copyright(C) 2018-2018
 * Author: wanhaoran
 * Date: 2018/7/21 17:11
 */
public class Main {
    static int minpath = Integer.MAX_VALUE;

    final static Point START = new Point(0,0);

    public static void caculate(Point start, Point[] points, int sum,int count) {

        for (int i = 0; i < points.length; i++) {
            if (points[i].isVisited == false) {
                points[i].isVisited = true;
                count++;
                sum += start.getLength(points[i]);
                if (count == points.length){
                    sum+=points[i].getLength(START);
                    if (sum<minpath){
                        minpath = sum;
                    }
                }
                caculate(points[i], points, sum,count);
                points[i].isVisited = false;
                count--;
                sum -= start.getLength(points[i]);
            }
        }

    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = Integer.parseInt(scanner.nextLine().trim());
        Point[] points = new Point[num];
        for (int i = 0; i < num; i++) {
            String[] locations = scanner.nextLine().trim().split(",");
            points[i] = new Point(Integer.parseInt(locations[0]), Integer.parseInt(locations[1]));
        }
        caculate(new Point(0,0),points,0,0);
        System.out.println(minpath);
    }
}


class Point {
    int x, y;
    boolean isVisited;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
        this.isVisited = false;
    }

    public int getLength(Point point) {
        return Math.abs(this.x - point.x) + Math.abs(this.y - point.y);
    }
}