华为OD机试真题 2026-9-2【无人机巡检航线规划】

无人机巡检航线规划(Java/Py/C/C++/Js/Go)题解

华为OD机试真题 新系统 华为OD上机考试真题新系统 9月2号 200分题型

华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录｜机考题库 + 算法考点详解

题目内容

某电力公司使用无人机对

n

n

n 个电力塔进行巡检。每个电力塔

i

i

i 位于坐标

(

x

i

,

y

i

)

(x_i, y_i)

(xi​,yi​)，无人机从基地（坐标

(

0

,

0

)

(0,0)

(0,0)）出发，需要依次飞达每个电力塔完成巡检后结束任务，无需返回基地。 无人机同一时刻只能飞向一个电力塔，请规划巡检顺序，使无人机飞行的总距离最短（两个坐标点间按曼哈顿距离计算，即

∣

x

1

−

x

2

∣

+

∣

y

1

−

y

2

∣

|x_1-x_2| + |y_1-y_2|

∣x1​−x2​∣+∣y1​−y2​∣），输出最短总距离。

输入描述

• $n$
• $x_i,y_i$

输出描述

输出最短总距离（整数）

样例1

输入

3
1 2
3 1
2 3

输出

8

说明 3 个电力塔：

A

(

1

,

2

)

A(1,2)

A(1,2)、

B

(

3

,

1

)

B(3,1)

B(3,1)、

C

(

2

,

3

)

C(2,3)

C(2,3)。基地为

O

(

0

,

0

)

O(0,0)

O(0,0)。

• 巡检顺序 $A\to C\to B$
• 巡检顺序 $A\to B\to C$
• 巡检顺序 $B\to A\to C$

样例2

输入

2
1 1
2 2

输出

4

说明 2 个电力塔：

A

(

1

,

1

)

A(1,1)

A(1,1)、

B

(

2

,

2

)

B(2,2)

B(2,2)。基地为

O

(

0

,

0

)

O(0,0)

O(0,0)。

• 巡检顺序 $A\to B$
• 巡检顺序 $B\to A$

题解

思路：状态压缩DP

C++

#include<bits/stdc++.h>
#include <vector>
using namespace std;

// 计算曼哈顿距离
int distance(vector<vector<int>>& coordinate,int i, int j) {
return abs(coordinate[i][0] – coordinate[j][0])
+ abs(coordinate[i][1] – coordinate[j][1]);
}

int solve(vector<vector<int>>& coordinate) {
int n = coordinate.size();
int INF = INT_MAX / 2;

int maxState = 1 << n;
// dp[mask][i]：
// 已经访问mask中的所有塔，并且当前位于第i个塔的最短距离
vector<vector<int>> dp(maxState, vector<int>(n, INF));

// 从基地(0,0)出发，直接前往每一个塔
for (int i = 0; i < n; i++) {
dp[1 << i][i] = abs(coordinate[i][0]) + abs(coordinate[i][1]);
}

for (int mask = 0; mask < maxState; mask++) {
for (int i = 0; i < n; i++) {
// 第i个塔没有访问过
if ((mask & (1 << i)) == 0) {
continue;
}
// 当前状态不可达
if (dp[mask][i] == INF) {
continue;
}
// 去访问还没有访问的塔j
for (int j = 0; j < n; j++) {
if ((mask & (1 << j)) != 0) {
continue;
}

int newMask = mask | (1 << j);

dp[newMask][j] = min(
dp[newMask][j],
dp[mask][i] + distance(coordinate ,i, j)
);
}
}
}
int ans = INF;
int all = (1 << n) – 1;
for (int i = 0; i < n; i++) {
ans = min(ans, dp[all][i]);
}
return ans;
}

int main() {
int n;
cin >> n;
vector<vector<int>> coordinate(n, vector<int>(2));
for (int i = 0; i < n; i++) {
cin >> coordinate[i][0] >> coordinate[i][1];
}

cout << solve(coordinate);
return 0;
}

JAVA

import java.io.*;
import java.util.*;

public class Main {

// 计算曼哈顿距离
static int distance(int[][] coordinate, int i, int j) {
return Math.abs(coordinate[i][0] – coordinate[j][0])
+ Math.abs(coordinate[i][1] – coordinate[j][1]);
}

static int solve(int[][] coordinate) {
int n = coordinate.length;
int INF = Integer.MAX_VALUE / 2;

int maxState = 1 << n;

// dp[mask][i]：
// 已经访问mask中的所有塔，并且当前位于第i个塔的最短距离
int[][] dp = new int[maxState][n];

for (int i = 0; i < maxState; i++) {
Arrays.fill(dp[i], INF);
}

// 从基地(0,0)出发，直接前往每一个塔
for (int i = 0; i < n; i++) {
dp[1 << i][i] = Math.abs(coordinate[i][0])
+ Math.abs(coordinate[i][1]);
}

for (int mask = 0; mask < maxState; mask++) {
for (int i = 0; i < n; i++) {
// 第i个塔没有访问过
if ((mask & (1 << i)) == 0) {
continue;
}

// 当前状态不可达
if (dp[mask][i] == INF) {
continue;
}

// 去访问还没有访问的塔j
for (int j = 0; j < n; j++) {
if ((mask & (1 << j)) != 0) {
continue;
}

int newMask = mask | (1 << j);

dp[newMask][j] = Math.min(
dp[newMask][j],
dp[mask][i] + distance(coordinate, i, j)
);
}
}
}

int ans = INF;
int all = (1 << n) – 1;

for (int i = 0; i < n; i++) {
ans = Math.min(ans, dp[all][i]);
}

return ans;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int n = sc.nextInt();
int[][] coordinate = new int[n][2];

for (int i = 0; i < n; i++) {
coordinate[i][0] = sc.nextInt();
coordinate[i][1] = sc.nextInt();
}

System.out.println(solve(coordinate));
}
}

Python

import sys

# 计算曼哈顿距离
def distance(coordinate, i, j):
return abs(coordinate[i][0] – coordinate[j][0]) + \\
abs(coordinate[i][1] – coordinate[j][1])

def solve(coordinate):
n = len(coordinate)
INF = 10**9

maxState = 1 << n

# dp[mask][i]：
# 已经访问mask中的所有塔，并且当前位于第i个塔的最短距离
dp = [[INF] * n for _ in range(maxState)]

# 从基地(0,0)出发，直接前往每一个塔
for i in range(n):
dp[1 << i][i] = abs(coordinate[i][0]) + abs(coordinate[i][1])

for mask in range(maxState):
for i in range(n):
# 第i个塔没有访问过
if (mask & (1 << i)) == 0:
continue

# 当前状态不可达
if dp[mask][i] == INF:
continue

# 去访问还没有访问的塔j
for j in range(n):
if (mask & (1 << j)) != 0:
continue

newMask = mask | (1 << j)

dp[newMask][j] = min(
dp[newMask][j],
dp[mask][i] + distance(coordinate, i, j)
)

ans = INF
all = (1 << n) – 1

for i in range(n):
ans = min(ans, dp[all][i])

return ans

data = list(map(int, sys.stdin.buffer.read().split()))

n = data[0]
coordinate = []

index = 1
for i in range(n):
coordinate.append([data[index], data[index + 1]])
index += 2

print(solve(coordinate))

JavaScript

const readline = require("readline");

const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});

let input = [];

rl.on("line", (line) => {
input.push(…line.trim().split(/\\s+/).filter(Boolean));
});

rl.on("close", () => {
let index = 0;

const n = Number(input[index++]);
const coordinate = new Array(n);

for (let i = 0; i < n; i++) {
coordinate[i] = [
Number(input[index++]),
Number(input[index++])
];
}

// 计算曼哈顿距离
function distance(coordinate, i, j) {
return Math.abs(coordinate[i][0] – coordinate[j][0])
+ Math.abs(coordinate[i][1] – coordinate[j][1]);
}

function solve(coordinate) {
const n = coordinate.length;
const INF = Number.MAX_SAFE_INTEGER;

const maxState = 1 << n;

// dp[mask][i]：
// 已经访问mask中的所有塔，并且当前位于第i个塔的最短距离
const dp = Array.from(
{ length: maxState },
() => new Array(n).fill(INF)
);

// 从基地(0,0)出发，直接前往每一个塔
for (let i = 0; i < n; i++) {
dp[1 << i][i] =
Math.abs(coordinate[i][0]) +
Math.abs(coordinate[i][1]);
}

for (let mask = 0; mask < maxState; mask++) {
for (let i = 0; i < n; i++) {
// 第i个塔没有访问过
if ((mask & (1 << i)) === 0) {
continue;
}

// 当前状态不可达
if (dp[mask][i] === INF) {
continue;
}

// 去访问还没有访问的塔j
for (let j = 0; j < n; j++) {
if ((mask & (1 << j)) !== 0) {
continue;
}

const newMask = mask | (1 << j);

dp[newMask][j] = Math.min(
dp[newMask][j],
dp[mask][i] + distance(coordinate, i, j)
);
}
}
}

let ans = INF;
const all = (1 << n) – 1;

for (let i = 0; i < n; i++) {
ans = Math.min(ans, dp[all][i]);
}

return ans;
}

console.log(solve(coordinate));
});

Go

package main

import (
"bufio"
"fmt"
"os"
)

// 计算曼哈顿距离
func distance(coordinate [][]int, i int, j int) int {
return abs(coordinate[i][0]–coordinate[j][0]) +
abs(coordinate[i][1]–coordinate[j][1])
}

func abs(x int) int {
if x < 0 {
return –x
}
return x
}

func solve(coordinate [][]int) int {
n := len(coordinate)
INF := int(^uint(0) >> 1) / 2

maxState := 1 << n

// dp[mask][i]：
// 已经访问mask中的所有塔，并且当前位于第i个塔的最短距离
dp := make([][]int, maxState)

for i := 0; i < maxState; i++ {
dp[i] = make([]int, n)
for j := 0; j < n; j++ {
dp[i][j] = INF
}
}

// 从基地(0,0)出发，直接前往每一个塔
for i := 0; i < n; i++ {
dp[1<<i][i] = abs(coordinate[i][0]) +
abs(coordinate[i][1])
}

for mask := 0; mask < maxState; mask++ {
for i := 0; i < n; i++ {
// 第i个塔没有访问过
if (mask & (1 << i)) == 0 {
continue
}

// 当前状态不可达
if dp[mask][i] == INF {
continue
}

// 去访问还没有访问的塔j
for j := 0; j < n; j++ {
if (mask & (1 << j)) != 0 {
continue
}

newMask := mask | (1 << j)

value := dp[mask][i] + distance(coordinate, i, j)

if value < dp[newMask][j] {
dp[newMask][j] = value
}
}
}
}

ans := INF
all := (1 << n) – 1

for i := 0; i < n; i++ {
if dp[all][i] < ans {
ans = dp[all][i]
}
}

return ans
}

func main() {
reader := bufio.NewReader(os.Stdin)

var n int
fmt.Fscan(reader, &n)

coordinate := make([][]int, n)

for i := 0; i < n; i++ {
coordinate[i] = make([]int, 2)
fmt.Fscan(reader, &coordinate[i][0], &coordinate[i][1])
}

fmt.Println(solve(coordinate))
}

C语言

#include <stdio.h>
#include <stdlib.h>

int absValue(int x) {
return x < 0 ? –x : x;
}

// 计算曼哈顿距离
int distance(int coordinate[][2], int i, int j) {
return absValue(coordinate[i][0] – coordinate[j][0])
+ absValue(coordinate[i][1] – coordinate[j][1]);
}

int solve(int coordinate[][2], int n) {
int INF = 1000000000;

int maxState = 1 << n;

// dp[mask][i]：
// 已经访问mask中的所有塔，并且当前位于第i个塔的最短距离
int **dp = (int **)malloc(maxState * sizeof(int *));

for (int i = 0; i < maxState; i++) {
dp[i] = (int *)malloc(n * sizeof(int));

for (int j = 0; j < n; j++) {
dp[i][j] = INF;
}
}

// 从基地(0,0)出发，直接前往每一个塔
for (int i = 0; i < n; i++) {
dp[1 << i][i] =
absValue(coordinate[i][0]) +
absValue(coordinate[i][1]);
}

for (int mask = 0; mask < maxState; mask++) {
for (int i = 0; i < n; i++) {
// 第i个塔没有访问过
if ((mask & (1 << i)) == 0) {
continue;
}

// 当前状态不可达
if (dp[mask][i] == INF) {
continue;
}

// 去访问还没有访问的塔j
for (int j = 0; j < n; j++) {
if ((mask & (1 << j)) != 0) {
continue;
}

int newMask = mask | (1 << j);

int value = dp[mask][i] +
distance(coordinate, i, j);

if (value < dp[newMask][j]) {
dp[newMask][j] = value;
}
}
}
}

int ans = INF;
int all = (1 << n) – 1;

for (int i = 0; i < n; i++) {
if (dp[all][i] < ans) {
ans = dp[all][i];
}
}

// 释放内存
for (int i = 0; i < maxState; i++) {
free(dp[i]);
}
free(dp);

return ans;
}

int main() {
int n;
scanf("%d", &n);

int coordinate[15][2];

for (int i = 0; i < n; i++) {
scanf("%d %d",
&coordinate[i][0],
&coordinate[i][1]);
}

printf("%d", solve(coordinate, n));

return 0;
}

​