【华为OD机试真题】密码本加密 · 字典序最小路径搜索（C语言）

一、题目

有一种特殊的加密算法，明文为一段数字串，经过密码本查找转换，生成另一段密文数字串。规则如下：

1.明文为一段数字串由0-9组成。
2.密码本为数字0-9组成的二维数组。
3.需要按明文串的数字顺序在密码本里找到同样的数字串，密码本里的数字串是由相邻的单元格数字组成，上下和左右是相邻的，注意对角线不相邻，同一个单元格的数字不能重复使用。
4.每一位明文对应密文即为密码本中找到的单元格所在的行和列序号(序号从0开始)组成的两个数字。如明文第位Data[i]对应密码本单元格为Book[x][y]，则明文第位对应的密文为XY，X和Y之间用空格隔开。

如果有多条密文，返回字符序最小的密文。如果密码本无法匹配，返回"error"。

请你设计这个加密程序。

示例1:
密码本
[0 0 2]
[1 3 4]
[6 6 4]
明文:3,密文:"1 1"

示例2:
密码本:
0 0 2
1 3 4
6 6 4
明文:"0 3" 密文:"0 1 1 1"

输入描述
第一行输入1个正整数N,代表明文的长度 (1 <= N <= 200)
第二行输入N个明文数字组成的序列Data[i] (整数: 0<= Data[i] <= 9)
第三行1个正整数M，代表密文的长度，接下来M行，每行M个数，代表密文矩阵

输出描述
输出字典序最小密文。如果无法匹配，输出"error"

示例1：
输入：
2
0 3
3
0 0 2
1 3 4
6 6 4

输出：
0 1 1 1

示例2：
输入：

5

0 2
3 4
6 4
输出：
error

二、解题思路：C语言视角的挑战与对策

1. 核心算法：回溯 + 贪心

与高级语言一样，核心逻辑不变：

• 贪心策略：在每一步搜索时，优先尝试坐标值（行号小，其次列号小）更小的邻居节点。
• 早期终止：由于搜索顺序保证了字典序单调递增，第一条成功匹配完整明文的路径必然是全局最优解。找到后立即停止搜索。

2. C语言的实现难点与对策

C语言没有std::vector或List，需要手动管理内存和数据结构：

• 动态路径存储：
  • 对策：已知最大长度 N≤200 ，路径坐标数为 2N≤400 。可以直接定义足够大的静态数组int path[405]，用一个变量path_len模拟栈顶指针。
• 邻居节点排序：
  • 对策：每一步最多有4个邻居。定义一个小型结构体数组Point neighbors[4]，收集合法邻居后，使用标准库qsort进行排序。
• 访问标记：
  • 对策：使用二维数组int visited[105][105]（假设 M≤100 ）或动态分配的二维指针。为了代码简洁和速度，静态大数组通常是机考首选。
• 输入解析：
  • 对策：scanf会自动跳过空白符（空格、换行），非常适合处理这种数字序列输入。

三、C语言代码实现💻

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> // 定义最大限制，根据题目 N<=200, M通常<=100 #define MAX_N 205 #define MAX_M 105 #define MAX_PATH_LEN (MAX_N * 2) // 全局变量，避免递归传参过多 int N, M; int data[MAX_N]; int book[MAX_M][MAX_M]; int visited[MAX_M][MAX_M]; // 0:未访问, 1:已访问 int result_path[MAX_PATH_LEN]; int result_len = 0; bool found = false; // 坐标结构体 typedef struct { int x, y; } Point; // 方向数组：上、下、左、右 const int dx[4] = {-1, 1, 0, 0}; const int dy[4] = {0, 0, -1, 1}; // qsort 比较函数：按行号升序，行号相同按列号升序 int compare_points(const void *a, const void *b) { Point *p1 = (Point *)a; Point *p2 = (Point *)b; if (p1->x != p2->x) { return p1->x - p2->x; } return p1->y - p2->y; } /** * 深度优先搜索 * @param idx 当前匹配明文的索引 (0-based) * @param x 当前行 * @param y 当前列 * @param path 当前路径数组 * @param path_len 当前路径长度 */ void dfs(int idx, int x, int y, int *path, int path_len) { // 剪枝：如果已经找到最优解，直接返回 if (found) return; // 终止条件：匹配完成 if (idx == N) { // 复制结果 result_len = path_len; memcpy(result_path, path, sizeof(int) * path_len); found = true; return; } int target = data[idx]; Point neighbors[4]; int neighbor_count = 0; // 1. 收集合法邻居 for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < M && ny >= 0 && ny < M) { if (!visited[nx][ny] && book[nx][ny] == target) { neighbors[neighbor_count].x = nx; neighbors[neighbor_count].y = ny; neighbor_count++; } } } // 2. 对邻居排序 (关键步骤) if (neighbor_count > 0) { qsort(neighbors, neighbor_count, sizeof(Point), compare_points); } // 3. 按排序顺序递归 for (int i = 0; i < neighbor_count; i++) { int nx = neighbors[i].x; int ny = neighbors[i].y; // 标记 visited[nx][ny] = 1; path[path_len] = nx; path[path_len + 1] = ny; // 递归 dfs(idx + 1, nx, ny, path, path_len + 2); // 如果找到了，立即返回，无需回溯清理（因为不再需要其他解） if (found) return; // 回溯：取消标记 visited[nx][ny] = 0; // path 不需要显式 pop，因为下一次循环会覆盖，或者递归返回后 path_len 逻辑上减小 } } int main() { // 优化输入速度（虽然 scanf 通常够快） // 读取 N if (scanf("%d", &N) != 1) return 0; // 读取明文 for (int i = 0; i < N; i++) { scanf("%d", &data[i]); } // 读取 M if (scanf("%d", &M) != 1) return 0; // 读取矩阵 for (int i = 0; i < M; i++) { for (int j = 0; j < M; j++) { scanf("%d", &book[i][j]); } } // 初始化 visited memset(visited, 0, sizeof(visited)); found = false; result_len = 0; // 1. 收集并排序所有起点 Point starts[MAX_M * MAX_M]; int start_count = 0; for (int i = 0; i < M; i++) { for (int j = 0; j < M; j++) { if (book[i][j] == data[0]) { starts[start_count].x = i; starts[start_count].y = j; start_count++; } } } // 对起点排序 if (start_count > 0) { qsort(starts, start_count, sizeof(Point), compare_points); } // 2. 尝试每个起点 int current_path[MAX_PATH_LEN]; for (int i = 0; i < start_count; i++) { int sx = starts[i].x; int sy = starts[i].y; visited[sx][sy] = 1; current_path[0] = sx; current_path[1] = sy; dfs(1, sx, sy, current_path, 2); if (found) break; // 回溯起点 visited[sx][sy] = 0; } // 3. 输出结果 if (found) { for (int i = 0; i < result_len; i++) { printf("%d%s", result_path[i], (i == result_len - 1) ? "" : " "); } printf("\n"); } else { printf("error\n"); } return 0; }

四、关键技术点解析🔍

1. 手动模拟栈（Path Management）

在 C++ 中我们用vector::push_back/pop_back，在 C 中：

• 定义一个大数组int path[405]。
• 传递path_len表示当前有效长度。
• 入栈：path[path_len] = val; path_len++;
• 出栈：逻辑上只需path_len -= 2（因为每次加两个坐标），或者在下一次循环直接覆盖。
• 优势：避免了malloc/free的频繁调用，极大提升性能且无内存泄漏风险。

2.qsort的灵活应用

C 标准库<stdlib.h>中的qsort是排序利器。

• 我们定义了Point结构体。
• 编写compare_points回调函数，实现先比行、再比列的逻辑。
• 在 DFS 的每一层，对最多 4 个邻居进行排序，开销几乎可以忽略不计，但保证了搜索方向的贪心性。

3. 全局状态与重置

• 使用全局数组visited和found标志位，减少递归参数传递，使代码更清晰。
• 注意：在找到解后 (if (found) return;)，我们故意不进行回溯清理（即不将visited设回 0），因为程序即将结束输出结果。这是一种微小的优化。只有在探索失败分支时才必须严格回溯。

4. 输入处理的鲁棒性

• scanf("%d")会自动忽略输入流中的空格、制表符和换行符。无论测试用例是将数字放在一行还是多行，代码都能正确解析，无需像某些语言那样手动处理字符串分割。

五、总结与备考建议🚀

这道题是 C 语言考察指针操作、数组管理和算法逻辑的综合题。

• 核心思想：利用搜索顺序的控制来替代结果集的排序，这是解决“字典序最值”类搜索问题的通用金钥匙。
• C语言优势：虽然没有 STL，但通过静态数组和简单的结构体，我们可以写出比 C++ 更高效（无动态分配开销）、更底层的代码。
• 避坑指南：
  • 务必检查数组越界。
  • visited数组的回溯逻辑要严密（除非已找到解）。
  • 输出格式严格要求空格分隔，行末无多余空格。

掌握这种“静态数组 + 手动栈 + qsort 贪心”的模式，你不仅能搞定华为OD，也能应对大多数嵌入式或高性能计算场景下的算法面试。

祝各位Coder编译一次过，运行无Bug！欢迎点赞收藏，持续更新C语言机试题解！