目录
题目
思路
Code
题目
题目内容：
某电力公司使用无人机对 n 个电力塔进行巡检。每个电力塔 i 位于坐标 (xi,yi)，无人机从基地（坐标 (0,0)）出发，需要依次飞达每个电力塔完成巡检后结束任务，无需返回基地。
无人机同一时刻只能飞向一个电力塔，请规划巡检顺序，使无人机飞行的总距离最短（两个坐标点间按曼哈顿距离计算，即 ∣x1−x2∣+∣y1−y2∣），输出最短总距离。
输入描述：
第一行输入 n，1 <= n <= 15。第二行输入 n 个坐标组成的二维数组，0 <= xi,yi <= 200。
输出描述：
输出最短总距离。
样例 1
输入：
3 [[1,2],[3,1],[2,3]]输出：
8样例 2
输入：
2 [[1,1],[2,2]]输出：
4思路
整体思路：用状态压缩动态规划枚举访问集合与当前终点。
第一步：预处理任意两塔之间的曼哈顿距离。
第二步：dp[mask][i] 表示访问 mask 且最后位于 i 的最短距离，单点状态由基地距离初始化。
第三步：从每个可达状态向未访问塔转移。
边界处理：无需返航，完整集合下取任意终点的最小值；n=1 时答案是基地距离。
复杂度分析：时间 O(2^n*n^2)，空间 O(2^n*n)。
Code
import re import sys lines = sys.stdin.read().splitlines() n = int(lines[0]) # 第一行之后每两个整数按顺序还原为一座塔的坐标。 # coords[i] 保存第 i 座塔的横纵坐标，dist[i][j] 保存从塔 i 直接飞到塔 j 的曼哈顿距离。 numbers = list(map(int, re.findall(r"\d+", "".join(lines[1:])))) coords = [[numbers[2 * i], numbers[2 * i + 1]] for i in range(n)] dist = [[abs(coords[i][0] - coords[j][0]) + abs(coords[i][1] - coords[j][1]) for j in range(n)] for i in range(n)] full = (1 << n) - 1 infinity = 10**9 # dp[mask][last] 表示访问 mask 中全部塔且最后停在 last 的最短距离。 # mask 的二进制第 i 位为 1 表示第 i 座塔已经巡检，last 是当前航线最后停留的塔。 dp = [[infinity] * n for _ in range(1 << n)] for i, (x, y) in enumerate(coords): # 单点状态是基地到第一座塔的曼哈顿距离，任务结束无需返航。 # 状态 1<JS
const fs = require("fs"); const numbers = (fs.readFileSync(0, "utf8").match(/\d+/g) || []).map(Number); const n = numbers[0]; // 首整数是塔数，后续每两个整数构成塔坐标。 // coords[i] 保存第 i 座塔的横纵坐标，dist[i][j] 保存从塔 i 直接飞到塔 j 的曼哈顿距离。 const coords = Array.from({ length: n }, (_, i) => [ numbers[1 + 2 * i], numbers[2 + 2 * i], ]); const dist = Array.from({ length: n }, () => Array(n).fill(0)); for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { dist[i][j] = Math.abs(coords[i][0] - coords[j][0]) + Math.abs(coords[i][1] - coords[j][1]); } } const states = 1 << n, infinity = 1e9; // dp[mask][last] 表示访问 mask 后停在 last 的最短距离。 // mask 的二进制第 i 位为 1 表示第 i 座塔已经巡检，last 是当前航线最后停留的塔。 const dp = Array.from({ length: states }, () => Array(n).fill(infinity)); // 状态 1<【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集
【华为od机试真题Python】：Python真题题库
【华为od机试真题JavaScript】：JavaScript真题题库
【华为od机试真题Java&Go】：Java&Go真题题库
【华为od机试真题C++】：C++真题题库
【华为od机试真题C语言】：C语言真题题库
【华为od面试手撕代码题库】：面试手撕代码题库
【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】
华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。