2023年华为OD机考真题：基站维修工程师

算法刷题1年前 (2023)更新江南白衣

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：基站维修工程师
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
小王是一名基站维护工程师，负责某区域的基站维护。
某地方有n个基站（1<n<10），已知各基站之间的距离s（0<s<500），并且基站x到基站y的距离，与基站y到基站x的距离并不一定会相同。
小王从基站1出发，途径每个基站1次，然后返回基站1，需要请你为他选择一条距离最短的路线。
输入描述：
站点数n和各站点之间的距离（均为整数）。如：
3 {站点数}
0 2 l {站点1到各站点的路程}
1 0 2 {站点2到各站点的路程}
2 1 0 {站点3到各站点的路程}
输出描述：
3
最短路程的数值
示例1
输入：
3
0 2 1
1 0 2
2 1 0
输出：
3
解题思路：
将各基站路程转化为二维数组
通过回溯的方法将所有可能的路线模拟一遍，找到最短的路程

Java代码实现：

package com.codernav.demo.hwod.exam;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @title 基站维修工程师
 * @Description 小王是一名基站维护工程师，负责某区域的基站维护。
 * 某地方有n个基站（1<n<10），已知各基站之间的距离s（0<s<500），并且基站x到基站y的距离，与基站y到基站x的距离并不一定会相同。
 * 小王从基站1出发，途径每个基站1次，然后返回基站1，需要请你为他选择一条距离最短的路线。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        int[][] distance = new int[n][n];   //路程转化为二维数组
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                distance[i][j] = sc.nextInt();
            }
        }
        for (int i = 1; i < distance.length; i++) {
            List<Integer> stepList = new ArrayList<>();
            stepList.add(i);    //从基站2开始走
            handle(distance, i, stepList, distance[0][i]);
        }
        System.out.println(min);
    }

    /**
     * @param ints  各基站路程的二维数组
     * @param index 达到的基站
     * @param step  路过的基站
     * @param sum   走过的路程
     */
    public static void handle(int[][] ints, int index, List<Integer> step, int sum) {
        if (step.size() + 1 == ints.length) {     //走完所有的基站，准备返回基站1
            min = Math.min(min, sum + ints[index][0]);     //记得加上基站1的路程
        } else {
            for (int i = 1; i < ints.length; i++) {
                if (step.contains(i)) {   //已经走过的基站不需要再走
                    continue;
                }
                step.add(i);    //走过的基站
                handle(ints, i, step, sum + ints[index][i]);    //index到达的基站，i下次去的基站
                step.remove(step.size() - 1);     //刚走过的基站需要剔除以便进行下一个循环
            }
        }
    }
}

满分代码实现：

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 基站维修工程师
 * @Description 小王是一名基站维护工程师，负责某区域的基站维护。
 * 某地方有n个基站（1<n<10），已知各基站之间的距离s（0<s<500），并且基站x到基站y的距离，与基站y到基站x的距离并不一定会相同。
 * 小王从基站1出发，途径每个基站1次，然后返回基站1，需要请你为他选择一条距离最短的路线。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        if (num <= 1) {
            System.out.println(0);
        }
        int[][] arr = new int[num][num];
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                arr[i][j] = in.nextInt();
            }
        }
        boolean visited[] = new boolean[num];
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < num; i++) {
            visited[i] = true;
            int temp = dfs(arr, visited, i, arr[0][i]);
            visited[i] = false;
            min = Math.min(temp, min);
        }
        System.out.println(min);
    }

    public static int dfs(int[][] arr, boolean[] visited, int curIndex, int len) {
        visited[curIndex] = true;
        if (judge(visited)) {
            visited[curIndex] = false;
            return len + arr[curIndex][0];
        }
        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= arr.length - 1; i++) {
            if (visited[i]) {
                continue;
            }
            int temp = dfs(arr, visited, i, len + arr[curIndex][i]);
            min = Math.min(temp, min);
        }
        visited[curIndex] = false;
        return min;
    }

    // 判断是否除0外，其余站点都已经经过
    public static boolean judge(boolean[] visited) {
        for (int i = 1; i < visited.length; i++) {
            if (!visited[i]) {
                return false;
            }
        }
        return true;
    }
}