#P4467. 第2题-无人机物流配送路径规划
-
1000ms
Tried: 84
Accepted: 16
Difficulty: 7
所属公司 :
华为
时间 :2025年11月12日-非AI方向(通软&嵌软&测试&算法&数据科学)
-
算法标签>BFS
第2题-无人机物流配送路径规划
解题思路
- 使用 BFS(广度优先搜索) 在网格上按步数分层扩展,首次到达终点即为最短路。
- 状态:
(r, c, rem),rem为还能连续飞行的步数;初始为k。 每次上下左右移动一步:rem-1;若落到充电站(值为2),则把rem重置为k。 - 剪枝:为每个格子
(r,c)维护best[r][c] = 到达该格子时见过的最大 rem。 若新到达的rem <= best[r][c],则该状态被更优状态支配,直接丢弃。 - 这样既保证最短步数,又控制状态数量;输入按空格分隔整数逐个读取,适配你给的样例格式。
复杂度分析
- 最坏上界
O(m*n*k);由于每格只在rem变大时才更新,实际接近O(m*n)。 - 空间复杂度
O(m*n)(best与队列)。
代码实现
Python
# 读取格式:全部按整数读取,支持以空格分隔的行
# 功能:BFS + 续航状态,落在充电站就把 rem 置为 k
import sys, re
from collections import deque
def shortest_path(m, n, grid, sr, sc, tr, tc, k):
best = [[-1]*n for _ in range(m)]
q = deque()
best[sr][sc] = k
q.append((sr, sc, k, 0)) # r,c,rem,dist
dirs = [(1,0),(-1,0),(0,1),(0,-1)]
while q:
r, c, rem, dist = q.popleft()
if r == tr and c == tc:
return dist
if rem == 0 and grid[r][c] != 2: # 没电且不在充电站,无法继续
continue
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != 1:
new_rem = k if grid[nr][nc] == 2 else rem - 1
if new_rem > best[nr][nc]:
best[nr][nc] = new_rem
q.append((nr, nc, new_rem, dist+1))
return -1
def main():
data = list(map(int, re.findall(r'-?\d+', sys.stdin.read())))
it = iter(data)
m = next(it); n = next(it)
grid = [[next(it) for _ in range(n)] for _ in range(m)]
sr, sc = next(it), next(it)
tr, tc = next(it), next(it)
k = next(it)
print(shortest_path(m, n, grid, sr, sc, tr, tc, k))
if __name__ == "__main__":
main()
Java
// 说明:使用自写的快速整数读取(兼容空格/换行/其它字符),适配“0 0 0”这种行。
// BFS + 剩余步数剪枝;类名 Main,ACM 风格。
import java.io.*;
import java.util.*;
public class Main {
// 简洁快读:读取下一个整数,跳过所有非数字字符
static class FastReader {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastReader(InputStream is){ in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, sign = 1, x = 0;
do { c = read(); } while (c != -1 && c <= ' '); // 跳过空白
if (c == '-') { sign = -1; c = read(); }
for (; c > ' '; c = read()) x = x * 10 + (c - '0');
return x * sign;
}
}
static int bfs(int[][] g, int sr, int sc, int tr, int tc, int k) {
int m = g.length, n = g[0].length;
int[][] best = new int[m][n];
for (int i = 0; i < m; i++) Arrays.fill(best[i], -1);
ArrayDeque<int[]> q = new ArrayDeque<>();
best[sr][sc] = k;
q.add(new int[]{sr, sc, k, 0}); // r,c,rem,dist
int[] dr = {1,-1,0,0};
int[] dc = {0,0,1,-1};
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1], rem = cur[2], dist = cur[3];
if (r == tr && c == tc) return dist;
if (rem == 0 && g[r][c] != 2) continue;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if (g[nr][nc] == 1) continue; // 障碍
int newRem = (g[nr][nc] == 2) ? k : rem - 1;
if (newRem > best[nr][nc]) {
best[nr][nc] = newRem;
q.add(new int[]{nr, nc, newRem, dist + 1});
}
}
}
return -1;
}
public static void main(String[] args) throws Exception {
FastReader fr = new FastReader(System.in);
int m = fr.nextInt(), n = fr.nextInt();
int[][] grid = new int[m][n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
grid[i][j] = fr.nextInt(); // 逐个整数读取,适配“0 0 0”格式
int sr = fr.nextInt(), sc = fr.nextInt();
int tr = fr.nextInt(), tc = fr.nextInt();
int k = fr.nextInt();
System.out.println(bfs(grid, sr, sc, tr, tc, k));
}
}
C++
// 说明:直接用 >> 读取整数(忽略空白),逐个读 m*n 个网格数,完全适配“0 0 0”格式。
// BFS + 剩余步数剪枝;ACM 风格。
#include <bits/stdc++.h>
using namespace std;
int bfs(const vector<vector<int>>& g, int sr, int sc, int tr, int tc, int k) {
int m = g.size(), n = g[0].size();
vector<vector<int>> best(m, vector<int>(n, -1));
queue<array<int,4>> q; // r,c,rem,dist
best[sr][sc] = k;
q.push({sr, sc, k, 0});
const int dr[4] = {1,-1,0,0};
const int dc[4] = {0,0,1,-1};
while (!q.empty()) {
auto cur = q.front(); q.pop();
int r = cur[0], c = cur[1], rem = cur[2], dist = cur[3];
if (r == tr && c == tc) return dist;
if (rem == 0 && g[r][c] != 2) continue;
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if (g[nr][nc] == 1) continue; // 障碍不可过
int newRem = (g[nr][nc] == 2) ? k : rem - 1;
if (newRem > best[nr][nc]) {
best[nr][nc] = newRem;
q.push({nr, nc, newRem, dist + 1});
}
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, n;
if (!(cin >> m >> n)) return 0;
vector<vector<int>> grid(m, vector<int>(n));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
cin >> grid[i][j];
int sr, sc, tr, tc, k;
cin >> sr >> sc >> tr >> tc >> k;
cout << bfs(grid, sr, sc, tr, tc, k) << '\n';
return 0;
}
题目内容
一家物流公司正在开发无人机配送系统。无人机需要从仓库出发,将包裹配送到指定的客户地点。配送区域被划分为一个二维网格,无人机每次可以向上、下、左、右四个方向移动一步。由于电池容量限制,无人机最多只能连续飞行k步,之后必须降落在充电站充电(如果没有充电站,则无法继续飞行)。请编写一个程序,计算无人机从起点到终点的最短路径长度。如果无法到达客户地点,返回 −1。
输入描述
配送区域大小:二维矩阵行数m,列数n,m和n的取值范围[1,1000]
配送区域表示:矩阵的大小为m×n,数值代表的意义如下:0 表示可飞行的空地。1 表示障碍物(如建筑物、树木等),无人机不能通过。2 表示充电站,无人机可以在此停留并充电。

起点:一个长度为 2 的列表,表示仓库的坐标start_row, start_col,左上角坐标为(0,0)
终点:一个长度为 2 的列表,表示客户地点的坐标destination_row, destination_col
k:无人机最多可以连续飞行的步数。取值范围[1,100000]
输出描述
返回无人机从仓库到客户地点的最短路径长度。如果无法到达客户地点,返回 −1。
样例1
输入
3 3
0 0 0
0 2 0
0 0 0
0 0
2 2
2
输出
4
说明
矩阵行数为 3,列数为 3
矩阵第一行为0 0 0
矩阵第二行为0 2 0
矩阵第三行为0 0 0
起点坐标为0 0
终点坐标为2 2
最多连续飞行步数为 2
无人机从(0, 0)出发,路径如下:
(0,0)→(0,1):步数 = 1,剩余可飞行步数 = 1
(0,1)→(1,1):步数 = 2,剩余可飞行步数 = 0
(1,1)是充电站,进入充电站后,剩余可飞行步数重置为 2
(1,1)→(2,1):步数 = 3,剩余可飞行步数 = 1
(2,1)→(2,2):步数 = 4,剩余可飞行步数 = 0
最短路径长度为 4
样例2
输入
3 3
0 0 0
1 1 1
0 0 0
0 0
2 2
2
输出
-1
说明
矩阵行数为 3,列数为 3
矩阵第一行为0 0 0
矩阵第二行为1 1 1
矩阵第三行为0 0 0
起点坐标为0 0
终点坐标为2 2
最多连续飞行步数为 2
无人机从(0, 0)出发,最多只能连续飞行 2 步,但到达(0, 2)后无法继续前进,因为没有充电站,所以无法到达(2, 2)。返回 - 1