笔试时间：2025年10月22日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

在自动驾驶系统中，车道线识别是核心功能之一。车道线通常具有连续性，从图像左侧到右侧逐渐展开。为了识别出最可能的车道线路径，我们可以在图像中找到一条路径，使得路径上所有像素的信号值与策略矩阵的乘积之和最大。现定义每个位置的能量值为策略矩阵与该位置周边信号值的乘积和。

给定一个 H×W 的图像以及一个 K×K 的策略矩阵，用于模拟不同方向的路径选择策略。你需要从图像的第一列任意像素出发，走到最后一列任意像素，每一步只能向右、右上、右下移动一格。在行进的过程中，需要实时的收集能量值，请找到一条路径，使得路径上的能量值之和最大。

提示： 策略矩阵为奇数，边缘处用零填充

输入描述

第一行输入 H W K K，分别表示给定图像及策略矩阵的维度

接下来：

• H 行输入图像矩阵
• K 行输入策略矩阵

输出描述

输出最大能量值

样例输入

1 1 1 1

5

1

样例输出

5.0

样例说明：

有且仅有一条路径，最大能量值为 5.0

参考题解

解题思路：

这个问题可以分解为两个关键步骤：

1. 计算能量图： 用策略矩阵对图像进行卷积，得到每个像素点的能量值 策略矩阵大小为K×K（K为奇数），相当于一个卷积核对图像每个位置(r,c)，计算其周边K×K区域与策略矩阵的乘积和边缘位置采用补零处理这样得到H×W的能量图，其中每个值表示该位置在策略矩阵作用下的能量
2. 动态规划找最优路径：状态定义：dp[r] 表示到达当前列第r行的最大累计能量状态转移：由于只能从左边、左上方、左下方三个方向过来： dp[r] = energy_map[r][c] + max(左边三个可能位置的最大值)具体来说：max(dp[r-1], dp[r], dp[r+1])（需要边界检查）

时间复杂度：O(H×W×K²) 用于能量图计算，O(H×W) 用于动态规划

C++：

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    int H, W, K, K2;
    cin >> H >> W >> K >> K2;
    
    vector<vector<int>> image(H, vector<int>(W));
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> image[i][j];
        }
    }
    
    vector<vector<int>> kernel(K, vector<int>(K));
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            cin >> kernel[i][j];
        }
    }
    
    // 计算能量图
    vector<vector<double>> energy_map(H, vector<double>(W, 0.0));
    int pad = (K - 1) / 2;
    
    for (int r = 0; r < H; r++) {
        for (int c = 0; c < W; c++) {
            double current_energy = 0.0;
            for (int i = 0; i < K; i++) {
                for (int j = 0; j < K; j++) {
                    int img_r = r + i - pad;
                    int img_c = c + j - pad;
                    int value = 0;
                    if (img_r >= 0 && img_r < H && img_c >= 0 && img_c < W) {
                        value = image[img_r][img_c];
                    }
                    current_energy += kernel[i][j] * value;
                }
            }
            energy_map[r][c] = current_energy;
        }
    }
    
    // 动态规划找最优路径
    vector<double> dp(H);
    for (int r = 0; r < H; r++) {
        dp[r] = energy_map[r][0];
    }
    
    for (int c = 1; c < W; c++) {
        vector<double> new_dp(H);
        for (int r = 0; r < H; r++) {
            double prev_max_energy = dp[r];
            if (r > 0) {
                prev_max_energy = max(prev_max_energy, dp[r - 1]);
            }
            if (r < H - 1) {
                prev_max_energy = max(prev_max_energy, dp[r + 1]);
            }
            new_dp[r] = energy_map[r][c] + prev_max_energy;
        }
        dp = new_dp;
    }
    
    double result = *max_element(dp.begin(), dp.end());
    cout << fixed << setprecision(1) << result << endl;
    
    return 0;
}

Java：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int W = sc.nextInt();
        int K = sc.nextInt();
        int K2 = sc.nextInt();
        
        int[][] image = new int[H][W];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                image[i][j] = sc.nextInt();
            }
        }
        
        int[][] kernel = new int[K][K];
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < K; j++) {
                kernel[i][j] = sc.nextInt();
            }
        }
        
        // 计算能量图
        double[][] energyMap = new double[H][W];
        int pad = (K - 1) / 2;
        
        for (int r = 0; r < H; r++) {
            for (int c = 0; c < W; c++) {
                double currentEnergy = 0.0;
                for (int i = 0; i < K; i++) {
                    for (int j = 0; j < K; j++) {
                        int imgR = r + i - pad;
                        int imgC = c + j - pad;
                        int value = 0;
                        if (imgR >= 0 && imgR < H && imgC >= 0 && imgC < W) {
                            value = image[imgR][imgC];