笔试时间：2025年8月10日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：无人机能耗最小化路径规划

在实际的无人机物流配送场景中，无人机需要从仓库(左上角网格点)出发，将货物送达目的地(右下角网格点)。为了优化飞行效率，我们将其飞行区域划分为m行n列的网格状单元格，每个单元格的数值表示该区域的单位能耗成本(非负整数，包含地形、风阻等因素影响)。由于无人机受限于飞行规则(如避免频繁转向、遵守临时禁飞区管制)，每次只能向右或向下移动一个单元格。请为无人机规划一条从起点到终点的飞行路径，使得全程的总能耗成本最小。

输入描述

第一行为两个整数，代表m和n，含义同题干描述，接下来一个m行n列的二维数组，数组中的每个整数代表对应网格的能耗成本.

输出描述

输出为正整数

样例输入

3 3

1 2 3

4 5 6

7 8 9

样例输出

21

参考题解

本题是线性动态规划的常见题型，动态规划定义：定义dp[i][j]为从起点 (0,0) 到单元格 (i,j) 的最小能耗 边界条件：第一行的单元格只能从左边移动过来，所以dp[0][j] = dp[0][j-1] + grid[0][j]第一列的单元格只能从上方移动过来，所以dp[i][0] = dp[i-1][0] + grid[i][0]状态转移方程：对于其他单元格，最小能耗等于上方或左方单元格的最小能耗加上当前单元格的能耗 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] 最终结果：dp[m-1][n-1]即为从起点到终点的最小总能耗。

C++：

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

long long calc_minimum_power_cost(const vector<vector<long long>>& grid) {
    int rows = grid.size();
    int cols = grid[0].size();
    vector<vector<long long>> dp(rows, vector<long long>(cols, 0));
    dp[0][0] = grid[0][0];
    for (int i = 1; i < rows; ++i) dp[i][0] = dp[i-1][0] + grid[i][0];
    for (int j = 1; j < cols; ++j) dp[0][j] = dp[0][j-1] + grid[0][j];
    for (int i = 1; i < rows; ++i)
        for (int j = 1; j < cols; ++j)
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
    return dp[rows-1][cols-1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n;
    if (!(cin >> m >> n)) return 0;
    if (m <= 0 || n <= 0) { cout << 0 << "\n"; return 0; }
    vector<vector<long long>> grid(m, vector<long long>(n));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)