全网最全面的华为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; } }
© 版权声明
文章版权归作者所有,未经允许请勿转载。
相关文章
暂无评论...