网站导航
> 技术文档 > 华为OD机试真题 E卷 C语言 实现【带传送阵的矩阵游离】_c语言 hashmap 华为

华为OD机试真题 E卷 C语言 实现【带传送阵的矩阵游离】_c语言 hashmap 华为

网友: 技术文档 2025-07-30 10:58:38

        所有题目均有五种语言实现。C实现目录、C++ 实现目录、Python实现目录、Java实现目录、JavaScript实现目录

题目

n 行 m 列的矩阵，每个位置上有一个元素
你可以上下左右行走，代价是前后两个位置元素值差的绝对值.
另外，你最多可以使用一次传送阵 (只能从一个数跳到另外一个相同的数)
求从走上角走到右下角最少需要多少时间。

输入描述：

第一行两个整数n,m，分别代表矩阵的行和列。

后面n行，每行m个整数，分别代表矩阵中的元素。

输出描述：

一个整数，表示最少需要多少时间。

示例1：

输入：

3 3

1 2 3

4 5 6

7 8 9

输出：

8

示例2：

输入：

3 3
1 2 3
4 5 6
7 1 4

输出：

3

思路

1：第一眼看像是BFS，但是由于可以【传送】，所以并不好求，因为算当前点到另外一个点的最小距离的时候，会受到其他点的影响。

2：首先计算左上角到每个点需要经过的最短时间，再计算右下角到每个点经过的最短时间。

，保存方式为map，key为每个点的数字，value为最小距离。然后将两个结果对应数字相加取出最小值即可。

3：具体代码逻辑如下：

  1. 输入解析

    • 读取输入的 n（行数）和 m（列数）。
    • 读取 n 行矩阵数据并存储。

  2. 计算从左上角到右下角的最短路径 (left_arr)

    • 逐行逐列遍历矩阵，计算到当前点的最短路径代价：
      • 第一行和第一列只能从左边或上方来，因此计算方式是累加绝对高度差。
      • 其他位置选择从上方或左侧过来的路径，取代价较小的路径累加。
    • 记录每个高度值的最小代价到 left_map。

  3. 计算从右下角到左上角的最短路径 (right_arr)

    • 采用类似方式，但遍历顺序是从右下角向左上角。
    • 记录每个高度值的最小代价到 right_map。

  4. 计算最终结果

    • 遍历所有高度值，找到 left_map 和 right_map 交汇处代价的最小值，即路径总代价最小的方案。

核心思路

  • 通过两次动态规划 (left_arr 和 right_arr)，分别计算从起点到终点的路径代价，并记录每个高度的最小路径值。
  • 通过寻找 left_map 和 right_map 交汇点的最小值，找到最优的路径组合。

输入输出

1 只有一个或几个输入
输入样例：

3 5 71

输入输出模板：

int main() {    int a, b, c;         // 接收有限个输入    cin >> a >> b >> c;      // 输出结果    cout << a+b+c << endl;}

2 先给元素个数，再给元素
先给行数T，再给出T行
输入样例：

33 5 76 8 912 9 51234

输入输出模板：

int main() {    int T;    vector res;      // 拿到输入行数T    cin >> T;      // 接收T行输入    while (T--) {        int a, b, c;        cin >> a >> b >> c;        res.push_back(a+b+c);    }      // 输出结果    for (int n : res) {        cout << n << endl;    }}

3  多组输入，读到文件结束符EOF为止
不直接告知有多少组输入，而是由EOF来判断。

方法一：

cin 读到有数据输入时会返回非0，而读到文件结束符时会返回0，结束while循环。

int main() {    int a, b;    vector res;    while (cin >> a >> b) {        res.push_back(a+b);    }}

方法二：

scanf 读到文件结束符时会返回-1，而-1的补码表示恰好是全1，从而用按位取反得到0，此时结束 while 循环。

int main() {    int a, b;    vector res;    while (~scanf(\"%d%d\", &a, &b)) {        res.push_back(a+b);    }}

4 字符串的输入
同样有 cin 和 scanf 两种方法

方法一：

int main() {    const int N = 100;    char s[N];    scanf(\"%s\", s);}

方法二：

int main() {    string s;    cin >> s;    cout << s << endl;}

字符串的输入有几点需要注意：C/C++ 中读入的字符串时包含结束符 \\0 的，我们需要的字符数组的长度要比真正的字符数加一；cin 和 scanf 两种读入方式都会忽略行首和行位的空格。

5 整行读取字符串
当我们不确定一行中是否有空格等特殊字符，我们可以使用 getline 进行整行读取：

int main() {    string s;    getline(cin, s);    cout << s << endl;}

默认以回车作为结束，如果需要自定义，可：

getline(cin, s, \'?\');

Code

#include #include #include #include #include #define MAX_N 900#define MAX_M 900#define MAX_MAP_SIZE 10000// 哈希表结构体typedef struct { int key; int value;} HashMap;HashMap left_map[MAX_MAP_SIZE];HashMap right_map[MAX_MAP_SIZE];int left_size = 0, right_size = 0;// 哈希表插入/更新函数void insert_or_update(HashMap *map, int *size, int key, int value) { for (int i = 0; i < *size; i++) { if (map[i].key == key) { if (value < map[i].value) { map[i].value = value; } return; } } map[*size].key = key; map[*size].value = value; (*size)++;}// 字符串拆分成整数数组int split(char *str, int *arr) { int count = 0; char *token = strtok(str, \" \"); while (token) { arr[count++] = atoi(token); token = strtok(NULL, \" \"); } return count;}int main() { char input[10000]; int matrix[MAX_N][MAX_M]; int left_arr[MAX_N][MAX_M] = {0}; int right_arr[MAX_N][MAX_M] = {0}; int n, m, distance; // 读取第一行 fgets(input, sizeof(input), stdin); int params[2]; split(input, params); n = params[0]; m = params[1]; // 读取矩阵 for (int i = 0; i < n; i++) { fgets(input, sizeof(input), stdin); split(input, matrix[i]); } // 从左上角到右下角计算距离 for (int i = 0; i < n; i++) { for (int k = 0; k = 0; i--) { for (int k = m - 1; k >= 0; k--) { if (i == n - 1 && k == m - 1) { distance = 0; } else if (i == n - 1) { distance = abs(matrix[i][k] - matrix[i][k + 1]) + right_arr[i][k + 1]; } else if (k == m - 1) { distance = abs(matrix[i][k] - matrix[i + 1][k]) + right_arr[i + 1][k]; } else { distance = fmin(  abs(matrix[i][k] - matrix[i + 1][k]) + right_arr[i + 1][k],  abs(matrix[i][k] - matrix[i][k + 1]) + right_arr[i][k + 1] ); } right_arr[i][k] = distance; insert_or_update(right_map, &right_size, matrix[i][k], distance); } } // 计算最小值 int res = INT_MAX; for (int i = 0; i < left_size; i++) { for (int j = 0; j < right_size; j++) { if (left_map[i].key == right_map[j].key) { res = fmin(res, left_map[i].value + right_map[j].value); } } } printf(\"%d\\n\", res); return 0;}

要求

时间限制：C/C++ 1秒，其他语言 2秒

空间限制：C/C++262144K，其他语言524288K

64bit IO Format：%lld

语言限定：
C（clang11）, C++（clang++11）, Pascal（fpc 3.0.2）, Java（javac 1.8）, Python2（2.7.3）, 
PHP(7.4.7), C#(mcs5.4), ObjC(gcc 5.4), Pythen3(3.9), JavaScript Node(12.18.2), JavaScript V8(6.0.0),
Sqlite(3.7.9), R(4.0.3), Go(1.14.4), Ruby(2.7.1), Swift(5.3), matlab(Octave 5.2), Pypy2(pypy2.7.13),
Pypy3(pypy3.6.1), Rust(1.44), Scala(2.11.12), Kotlin(1.4.10), Groovy(3.0.6), TypeScript(4.1.2), Mysql(8.0)

 更多题目链接：

华为OD 2025 最新最全机试题库及讲解，A+B+C+D+E卷题库大全。

Java题库: 2024华为OD机试（JAVA）真题【E卷+A卷+B卷+C卷+D卷】目录_华为od机试真题-CSDN博客

Python题库: 2024华为OD机试（Python）真题【E卷+A卷+B卷+C卷+D卷】目录_华为od机试好过吗-CSDN博客

C++题库: 2024华为OD机试（C++）真题【E卷+A卷+B卷+C卷+D卷】目录_华为od怎么知道考的是a卷还是b卷-CSDN博客

Js题库: 2024 华为OD机试（JavaScript）真题【E卷+A卷+B卷+C卷+D卷】目录_华为od 2023 q2b卷-CSDN博客

C语言题库: 2024 华为OD机试（C语言）真题【E卷+A卷+B卷+C卷+D卷】目录-CSDN博客

面试手撕题库: 2024华为OD面试手撕代码真题目录_华为od手撕代码-CSDN博客

网络标签：

相关问题