一、题目有一种特殊的加密算法明文为一段数字串经过密码本查找转换生成另一段密文数字串。规则如下1.明文为一段数字串由0-9组成。2.密码本为数字0-9组成的二维数组。3.需要按明文串的数字顺序在密码本里找到同样的数字串密码本里的数字串是由相邻的单元格数字组成上下和左右是相邻的注意对角线不相邻同一个单元格的数字不能重复使用。4.每一位明文对应密文即为密码本中找到的单元格所在的行和列序号(序号从0开始)组成的两个数字。如明文第位Data[i]对应密码本单元格为Book[x][y]则明文第位对应的密文为XYX和Y之间用空格隔开。如果有多条密文返回字符序最小的密文。如果密码本无法匹配返回error。请你设计这个加密程序。示例1:密码本[0 0 2][1 3 4][6 6 4]明文:3,密文:1 1示例2:密码本:0 0 21 3 46 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输入20 330 0 21 3 46 6 4输出0 1 1 1示例2输入50 23 46 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 // 定义最大限制根据题目 N200, 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语言机试题解
【华为OD机试真题】密码本加密 · 字典序最小路径搜索（C语言）
一、题目有一种特殊的加密算法明文为一段数字串经过密码本查找转换生成另一段密文数字串。规则如下1.明文为一段数字串由0-9组成。2.密码本为数字0-9组成的二维数组。3.需要按明文串的数字顺序在密码本里找到同样的数字串密码本里的数字串是由相邻的单元格数字组成上下和左右是相邻的注意对角线不相邻同一个单元格的数字不能重复使用。4.每一位明文对应密文即为密码本中找到的单元格所在的行和列序号(序号从0开始)组成的两个数字。如明文第位Data[i]对应密码本单元格为Book[x][y]则明文第位对应的密文为XYX和Y之间用空格隔开。如果有多条密文返回字符序最小的密文。如果密码本无法匹配返回error。请你设计这个加密程序。示例1:密码本[0 0 2][1 3 4][6 6 4]明文:3,密文:1 1示例2:密码本:0 0 21 3 46 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输入20 330 0 21 3 46 6 4输出0 1 1 1示例2输入50 23 46 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 // 定义最大限制根据题目 N200, 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语言机试题解
