解题思路

• 使用 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 \times n$，数值代表的意义如下：$0$ 表示可飞行的空地。$1$ 表示障碍物（如建筑物、树木等），无人机不能通过。$2$ 表示充电站，无人机可以在此停留并充电。

起点：一个长度为 2 的列表，表示仓库的坐标$\text{start\_row, start\_col}$，左上角坐标为$(0,0)$

终点：一个长度为 2 的列表，表示客户地点的坐标$\text{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) \to (0, 1)$：步数 = 1，剩余可飞行步数 = 1

$(0, 1) \to (1, 1)$：步数 = 2，剩余可飞行步数 = 0

$(1, 1)$是充电站，进入充电站后，剩余可飞行步数重置为 2

$(1, 1) \to (2, 1)$：步数 = 3，剩余可飞行步数 = 1

$(2, 1) \to (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