一、题目有一种特殊的加密算法明文为一段数字串经过密码本查找转换生成另一段密文数字串。规则如下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. 核心难点字典序最小 vs 搜索空间如果盲目搜索所有路径再排序时间复杂度将是指数级 O(4N) 在 N200 时必然超时。破局关键利用DFS深度优先搜索的特性配合贪心排序。2. 算法策略有序搜索 自动排序字典序的比较是从左到右依次比较数值大小。如果我们能保证起点选择按(行, 列)从小到大遍历。每一步扩展将合法的相邻节点按(行, 列)从小到大排序后遍历。那么DFS 搜索树中第一条成功到达终点的路径其每一位坐标都是在当前约束下能取到的最小值。因此找到第一条路径即可直接返回无需继续搜索3. 实现细节数据结构使用vectorvectorint存储矩阵。使用vectorvectorbool记录访问状态visited。使用vectorint存储当前路径坐标。排序优化在每一层递归中收集所有合法邻居放入vectorpairint,int调用std::sort排序后再递归。虽然增加了每层的排序开销常数很小最多4个元素但换来了全局剪枝总体效率极高。输入处理使用cin配合循环读取自动跳过空白符处理多行输入更稳健。三、C 代码实现#include iostream #include vector #include algorithm #include numeric using namespace std; // 全局变量定义方便递归访问 int N, M; vectorint data; vectorvectorint book; vectorvectorbool visited; vectorint resultPath; bool found false; // 方向数组上、下、左、右 const int dx[4] {-1, 1, 0, 0}; const int dy[4] {0, 0, -1, 1}; // 坐标结构体用于排序 struct Point { int x, y; }; /** * 深度优先搜索 * param idx 当前匹配到明文的第几位 (0-based) * param x 当前行坐标 * param y 当前列坐标 * param path 当前已走过的路径坐标序列 */ void dfs(int idx, int x, int y, vectorint path) { // 剪枝如果已经找到最优解直接返回不再搜索 if (found) return; // 终止条件成功匹配完所有明文数字 if (idx N) { resultPath path; found true; return; } int target data[idx]; vectorPoint neighbors; // 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 !visited[nx][ny] book[nx][ny] target) { neighbors.push_back({nx, ny}); } } // 2. 关键步骤对邻居按字典序排序 (先比行再比列) // 由于邻居最多只有4个sort开销极小 sort(neighbors.begin(), neighbors.end(), [](const Point a, const Point b) { if (a.x ! b.x) return a.x b.x; return a.y b.y; }); // 3. 按排序后的顺序尝试递归 for (const auto p : neighbors) { // 标记访问 visited[p.x][p.y] true; path.push_back(p.x); path.push_back(p.y); // 递归下一层 dfs(idx 1, p.x, p.y, path); // 如果找到了直接返回不需要回溯因为不需要找其他解了 if (found) return; // 回溯取消标记弹出路径 path.pop_back(); path.pop_back(); visited[p.x][p.y] false; } } int main() { // 优化IO速度 ios::sync_with_stdio(false); cin.tie(nullptr); // --- 输入处理 --- if (!(cin N)) return 0; data.resize(N); for (int i 0; i N; i) { cin data[i]; } cin M; book.assign(M, vectorint(M)); visited.assign(M, vectorbool(M, false)); for (int i 0; i M; i) { for (int j 0; j M; j) { cin book[i][j]; } } // --- 核心逻辑 --- // 1. 收集所有可能的起点 (值为 data[0]) vectorPoint starts; for (int i 0; i M; i) { for (int j 0; j M; j) { if (book[i][j] data[0]) { starts.push_back({i, j}); } } } // 2. 起点按字典序排序 sort(starts.begin(), starts.end(), [](const Point a, const Point b) { if (a.x ! b.x) return a.x b.x; return a.y b.y; }); // 3. 依次尝试每个起点 for (const auto start : starts) { visited[start.x][start.y] true; vectorint path; path.reserve(N * 2); // 预分配内存 path.push_back(start.x); path.push_back(start.y); dfs(1, start.x, start.y, path); if (found) break; // 找到最优解跳出循环 // 回溯起点状态 visited[start.x][start.y] false; } // --- 输出结果 --- if (found) { for (size_t i 0; i resultPath.size(); i) { cout resultPath[i] (i resultPath.size() - 1 ? : ); } cout endl; } else { cout error endl; } return 0; }四、关键点深度解析1. 为什么sort邻居是必须的如果不排序DFS 会按照dx/dy定义的固定方向如上-下-左-右进行搜索。假设当前在(0,0)目标数字在(0,1)和(1,0)都有。固定方向可能先搜到(1,0)如果“下”排在“右”前面。但字典序要求(0,1)(即0 1) 优于(1,0)(即1 0)。结论必须在每一层动态收集邻居并排序确保总是优先尝试行号小、列号小的节点。2. 剪枝的高效性代码中if (found) return;是灵魂所在。传统回溯需要遍历整棵树来寻找所有解。本题利用贪心性质一旦found变为true所有递归层级立即逐层返回主循环也立即break。这使得算法在大多数有解的情况下只遍历一条有效路径及其少量失败分支效率接近 O(N×M2) 主要消耗在起点的查找和每层的常数次排序。3. C 特性应用ios::sync_with_stdio(false);关闭同步流大幅提升cin/cout速度防止因输入输出过慢导致超时。vector::reserve预分配路径向量内存减少动态扩容开销。lambda表达式在sort中使用 lambda 进行自定义比较代码简洁且高效。引用传递vectorint path使用引用传递避免递归时的深拷贝配合push_back/pop_back实现高效回溯。4. 边界与异常处理无解情况若循环结束found仍为false输出error。单字符明文逻辑天然支持dfs传入idx1时直接命中idxN终止条件。矩阵越界nx 0 nx M ...检查严谨。五、总结这道题是考察图论搜索与贪心策略结合的典型题目。思维转换从“找出所有解再排序”转变为“按顺序找第一个就是最优”。C 优势利用 STL 的sort和vector可以非常优雅地实现邻居排序和路径回溯执行效率极高。备考建议在机考中遇到“字典序最小/最大”的路径搜索题优先考虑有序DFS 早期终止模式这通常是唯一能过大数据的解法。希望这篇题解能帮助你彻底掌握此类问题如有任何疑问欢迎在评论区留言讨论。
【华为OD机试真题】密码本加密 · 字典序最小路径搜索（C++）
发布时间：2026/5/20 10:13:02
一、题目有一种特殊的加密算法明文为一段数字串经过密码本查找转换生成另一段密文数字串。规则如下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. 核心难点字典序最小 vs 搜索空间如果盲目搜索所有路径再排序时间复杂度将是指数级 O(4N) 在 N200 时必然超时。破局关键利用DFS深度优先搜索的特性配合贪心排序。2. 算法策略有序搜索 自动排序字典序的比较是从左到右依次比较数值大小。如果我们能保证起点选择按(行, 列)从小到大遍历。每一步扩展将合法的相邻节点按(行, 列)从小到大排序后遍历。那么DFS 搜索树中第一条成功到达终点的路径其每一位坐标都是在当前约束下能取到的最小值。因此找到第一条路径即可直接返回无需继续搜索3. 实现细节数据结构使用vectorvectorint存储矩阵。使用vectorvectorbool记录访问状态visited。使用vectorint存储当前路径坐标。排序优化在每一层递归中收集所有合法邻居放入vectorpairint,int调用std::sort排序后再递归。虽然增加了每层的排序开销常数很小最多4个元素但换来了全局剪枝总体效率极高。输入处理使用cin配合循环读取自动跳过空白符处理多行输入更稳健。三、C 代码实现#include iostream #include vector #include algorithm #include numeric using namespace std; // 全局变量定义方便递归访问 int N, M; vectorint data; vectorvectorint book; vectorvectorbool visited; vectorint resultPath; bool found false; // 方向数组上、下、左、右 const int dx[4] {-1, 1, 0, 0}; const int dy[4] {0, 0, -1, 1}; // 坐标结构体用于排序 struct Point { int x, y; }; /** * 深度优先搜索 * param idx 当前匹配到明文的第几位 (0-based) * param x 当前行坐标 * param y 当前列坐标 * param path 当前已走过的路径坐标序列 */ void dfs(int idx, int x, int y, vectorint path) { // 剪枝如果已经找到最优解直接返回不再搜索 if (found) return; // 终止条件成功匹配完所有明文数字 if (idx N) { resultPath path; found true; return; } int target data[idx]; vectorPoint neighbors; // 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 !visited[nx][ny] book[nx][ny] target) { neighbors.push_back({nx, ny}); } } // 2. 关键步骤对邻居按字典序排序 (先比行再比列) // 由于邻居最多只有4个sort开销极小 sort(neighbors.begin(), neighbors.end(), [](const Point a, const Point b) { if (a.x ! b.x) return a.x b.x; return a.y b.y; }); // 3. 按排序后的顺序尝试递归 for (const auto p : neighbors) { // 标记访问 visited[p.x][p.y] true; path.push_back(p.x); path.push_back(p.y); // 递归下一层 dfs(idx 1, p.x, p.y, path); // 如果找到了直接返回不需要回溯因为不需要找其他解了 if (found) return; // 回溯取消标记弹出路径 path.pop_back(); path.pop_back(); visited[p.x][p.y] false; } } int main() { // 优化IO速度 ios::sync_with_stdio(false); cin.tie(nullptr); // --- 输入处理 --- if (!(cin N)) return 0; data.resize(N); for (int i 0; i N; i) { cin data[i]; } cin M; book.assign(M, vectorint(M)); visited.assign(M, vectorbool(M, false)); for (int i 0; i M; i) { for (int j 0; j M; j) { cin book[i][j]; } } // --- 核心逻辑 --- // 1. 收集所有可能的起点 (值为 data[0]) vectorPoint starts; for (int i 0; i M; i) { for (int j 0; j M; j) { if (book[i][j] data[0]) { starts.push_back({i, j}); } } } // 2. 起点按字典序排序 sort(starts.begin(), starts.end(), [](const Point a, const Point b) { if (a.x ! b.x) return a.x b.x; return a.y b.y; }); // 3. 依次尝试每个起点 for (const auto start : starts) { visited[start.x][start.y] true; vectorint path; path.reserve(N * 2); // 预分配内存 path.push_back(start.x); path.push_back(start.y); dfs(1, start.x, start.y, path); if (found) break; // 找到最优解跳出循环 // 回溯起点状态 visited[start.x][start.y] false; } // --- 输出结果 --- if (found) { for (size_t i 0; i resultPath.size(); i) { cout resultPath[i] (i resultPath.size() - 1 ? : ); } cout endl; } else { cout error endl; } return 0; }四、关键点深度解析1. 为什么sort邻居是必须的如果不排序DFS 会按照dx/dy定义的固定方向如上-下-左-右进行搜索。假设当前在(0,0)目标数字在(0,1)和(1,0)都有。固定方向可能先搜到(1,0)如果“下”排在“右”前面。但字典序要求(0,1)(即0 1) 优于(1,0)(即1 0)。结论必须在每一层动态收集邻居并排序确保总是优先尝试行号小、列号小的节点。2. 剪枝的高效性代码中if (found) return;是灵魂所在。传统回溯需要遍历整棵树来寻找所有解。本题利用贪心性质一旦found变为true所有递归层级立即逐层返回主循环也立即break。这使得算法在大多数有解的情况下只遍历一条有效路径及其少量失败分支效率接近 O(N×M2) 主要消耗在起点的查找和每层的常数次排序。3. C 特性应用ios::sync_with_stdio(false);关闭同步流大幅提升cin/cout速度防止因输入输出过慢导致超时。vector::reserve预分配路径向量内存减少动态扩容开销。lambda表达式在sort中使用 lambda 进行自定义比较代码简洁且高效。引用传递vectorint path使用引用传递避免递归时的深拷贝配合push_back/pop_back实现高效回溯。4. 边界与异常处理无解情况若循环结束found仍为false输出error。单字符明文逻辑天然支持dfs传入idx1时直接命中idxN终止条件。矩阵越界nx 0 nx M ...检查严谨。五、总结这道题是考察图论搜索与贪心策略结合的典型题目。思维转换从“找出所有解再排序”转变为“按顺序找第一个就是最优”。C 优势利用 STL 的sort和vector可以非常优雅地实现邻居排序和路径回溯执行效率极高。备考建议在机考中遇到“字典序最小/最大”的路径搜索题优先考虑有序DFS 早期终止模式这通常是唯一能过大数据的解法。希望这篇题解能帮助你彻底掌握此类问题如有任何疑问欢迎在评论区留言讨论。
