一、题目有一种特殊的加密算法明文为一段数字串经过密码本查找转换生成另一段密文数字串。规则如下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二、解题思路为什么“第一个”就是“最小”本题的难点在于“字典序最小”。通常的思路是找出所有路径 - 转换为字符串 - 排序 - 取最小。但在 N 高达 200 的情况下路径数量可能是指数级的全量搜索会导致TLE(超时)。1、核心优化贪心搜索顺序✅字典序的比较是从左到右的。如果我们能保证在搜索的每一步都优先尝试坐标值更小的选项那么深度优先搜索DFS就是字典序最小的路径。具体策略起点排序遍历矩阵找到所有等于data[0]的点按(行, 列)从小到大排序依次作为起点尝试。邻居排序在 DFS 的每一步收集所有合法的相邻点值匹配且未访问同样按(行, 列)从小到大排序。早期终止一旦某条路径成功匹配完整个明文序列立即返回结果不再搜索其他分支。结论无需存储所有路径无需最后排序。搜索顺序即排序顺序。2、算法流程解析输入构建矩阵。收集所有可能的起点坐标排序。对每个起点执行DFS标记当前点已访问。若已匹配完所有字符记录路径并返回True。否则获取下一位明文所需的相邻点排序后递归。若递归返回True直接向上返回True剪枝。若递归失败回溯取消标记弹出路径。若所有起点尝试完毕仍未找到输出error。三、代码实现1. Python实现Python 的列表推导式和递归非常适合此类问题。注意使用sys.stdin处理多行输入。import sys # 增加递归深度防止 N200 时爆栈 sys.setrecursionlimit(2000) def solve(): # --- 输入处理 --- input_data sys.stdin.read().split() if not input_data: return iterator iter(input_data) try: N int(next(iterator)) data [int(next(iterator)) for _ in range(N)] M int(next(iterator)) book [] for _ in range(M): row [int(next(iterator)) for _ in range(M)] book.append(row) except StopIteration: return # --- 核心逻辑 --- # 方向上下左右 directions [(-1, 0), (1, 0), (0, -1), (0, 1)] visited [[False] * M for _ in range(M)] result_path [] def dfs(idx, x, y, path): # 终止条件匹配完成 if idx N: return True target data[idx] neighbors [] # 收集合法邻居 for dx, dy in directions: nx, ny x dx, y dy if 0 nx M and 0 ny M: if not visited[nx][ny] and book[nx][ny] target: neighbors.append((nx, ny)) # 关键步骤按字典序排序邻居 (先比行再比列) neighbors.sort(keylambda p: (p[0], p[1])) for nx, ny in neighbors: visited[nx][ny] True path.append(nx) path.append(ny) if dfs(idx 1, nx, ny, path): return True # 回溯 path.pop() path.pop() visited[nx][ny] False return False # 1. 收集并排序所有起点 starts [] for i in range(M): for j in range(M): if book[i][j] data[0]: starts.append((i, j)) starts.sort(keylambda p: (p[0], p[1])) # 2. 依次尝试起点 found False for sx, sy in starts: visited[sx][sy] True current_path [sx, sy] if dfs(1, sx, sy, current_path): result_path current_path found True break visited[sx][sy] False # --- 输出 --- if found: print( .join(map(str, result_path))) else: print(error) if __name__ __main__: solve()2. JavaScript实现JS 需要注意异步输入流的读取以及数组的浅拷贝/回溯处理。const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); let lines []; let lineIndex 0; rl.on(line, (line) { lines.push(line.trim()); }); rl.on(close, () { // 扁平化所有输入 token const tokens lines.join( ).split(/\s/).filter(t t ! ); if (tokens.length 0) return; let idx 0; const N parseInt(tokens[idx]); const data []; for (let i 0; i N; i) { data.push(parseInt(tokens[idx])); } const M parseInt(tokens[idx]); const book []; for (let i 0; i M; i) { const row []; for (let j 0; j M; j) { row.push(parseInt(tokens[idx])); } book.push(row); } // 方向上下左右 const dirs [[-1, 0], [1, 0], [0, -1], [0, 1]]; const visited Array.from({ length: M }, () Array(M).fill(false)); let resultPath null; function dfs(currentIdx, x, y, path) { if (currentIdx N) { resultPath [...path]; return true; } const target data[currentIdx]; const neighbors []; for (const [dx, dy] of dirs) { const nx x dx; const ny y dy; if (nx 0 nx M ny 0 ny M) { if (!visited[nx][ny] book[nx][ny] target) { neighbors.push([nx, ny]); } } } // 排序邻居行优先列次之 neighbors.sort((a, b) { if (a[0] ! b[0]) return a[0] - b[0]; return a[1] - b[1]; }); for (const [nx, ny] of neighbors) { visited[nx][ny] true; path.push(nx, ny); if (dfs(currentIdx 1, nx, ny, path)) { return true; // 找到即返回 } // 回溯 path.pop(); path.pop(); visited[nx][ny] false; } return false; } // 收集起点 const starts []; for (let i 0; i M; i) { for (let j 0; j M; j) { if (book[i][j] data[0]) { starts.push([i, j]); } } } // 排序起点 starts.sort((a, b) { if (a[0] ! b[0]) return a[0] - b[0]; return a[1] - b[1]; }); let found false; for (const [sx, sy] of starts) { visited[sx][sy] true; const path [sx, sy]; if (dfs(1, sx, sy, path)) { found true; break; } visited[sx][sy] false; } if (found) { console.log(resultPath.join( )); } else { console.log(error); } });四、关键点解析与避坑1. 为什么不用比较所有路径很多初学者会写出“收集所有路径 -sort()- 取第一个”的代码。风险当 N200且矩阵中数字重复度高时路径数量可能达到天文数字内存溢出或超时。正解利用DFS 的贪心性质。只要我们在每一层递归都严格按照坐标从小到大遍历子节点第一条触达终点的路径必然是字典序最小的。这就像在字典里查单词按字母顺序找找到的第一个一定是排在前面的。2. 回溯的细节状态恢复在递归调用返回后无论成功与否只要不是直接向上返回成功必须将visited重置为false并将path中追加的坐标弹出。路径传递Python/JS 中列表/数组是引用传递。建议在递归参数中直接复用同一个列表通过push和pop维护状态避免每次递归都slice或copy数组这样能显著减少内存开销和时间消耗。3. 输入处理的陷阱多空格/换行测试用例中数字之间可能有多个空格或者换行不规范。Python:sys.stdin.read().split()会自动处理所有空白符空格、换行、制表符是最稳健的方式。JS:line.trim().split(/\s/)配合流式读取或者像示例中那样先合并再分割。边界检查矩阵坐标越界判断0 nx M必不可少。4. 特殊场景无解如果明文中的某个数字在矩阵中根本不存在或者虽然存在但无法形成连通路径循环结束后需输出error。单字符明文 N1 时只需找到字典序最小的那个数字的坐标即可代码逻辑天然支持dfs初始调用idx1直接命中终止条件。五、总结这道题是考察回溯算法与贪心思想结合的经典案例。核心技巧通过控制搜索顺序来替代结果排序。语言特性Python代码简洁sort和列表操作非常直观适合快速解题。JavaScript需注意异步 IO 处理和数组引用的回溯细节逻辑与 Python 高度一致。掌握这种“有序搜索 剪枝”的模式不仅能解决本题还能应用到许多类似的“求最小/最大路径”、“字典序排列”等图论搜索问题中。祝大家在机考中旗开得胜如有疑问欢迎评论区交流
【华为OD机试真题】密码本加密 · 字典序最小路径搜索（Python/JS）
发布时间：2026/5/20 6:52:14
一、题目有一种特殊的加密算法明文为一段数字串经过密码本查找转换生成另一段密文数字串。规则如下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二、解题思路为什么“第一个”就是“最小”本题的难点在于“字典序最小”。通常的思路是找出所有路径 - 转换为字符串 - 排序 - 取最小。但在 N 高达 200 的情况下路径数量可能是指数级的全量搜索会导致TLE(超时)。1、核心优化贪心搜索顺序✅字典序的比较是从左到右的。如果我们能保证在搜索的每一步都优先尝试坐标值更小的选项那么深度优先搜索DFS就是字典序最小的路径。具体策略起点排序遍历矩阵找到所有等于data[0]的点按(行, 列)从小到大排序依次作为起点尝试。邻居排序在 DFS 的每一步收集所有合法的相邻点值匹配且未访问同样按(行, 列)从小到大排序。早期终止一旦某条路径成功匹配完整个明文序列立即返回结果不再搜索其他分支。结论无需存储所有路径无需最后排序。搜索顺序即排序顺序。2、算法流程解析输入构建矩阵。收集所有可能的起点坐标排序。对每个起点执行DFS标记当前点已访问。若已匹配完所有字符记录路径并返回True。否则获取下一位明文所需的相邻点排序后递归。若递归返回True直接向上返回True剪枝。若递归失败回溯取消标记弹出路径。若所有起点尝试完毕仍未找到输出error。三、代码实现1. Python实现Python 的列表推导式和递归非常适合此类问题。注意使用sys.stdin处理多行输入。import sys # 增加递归深度防止 N200 时爆栈 sys.setrecursionlimit(2000) def solve(): # --- 输入处理 --- input_data sys.stdin.read().split() if not input_data: return iterator iter(input_data) try: N int(next(iterator)) data [int(next(iterator)) for _ in range(N)] M int(next(iterator)) book [] for _ in range(M): row [int(next(iterator)) for _ in range(M)] book.append(row) except StopIteration: return # --- 核心逻辑 --- # 方向上下左右 directions [(-1, 0), (1, 0), (0, -1), (0, 1)] visited [[False] * M for _ in range(M)] result_path [] def dfs(idx, x, y, path): # 终止条件匹配完成 if idx N: return True target data[idx] neighbors [] # 收集合法邻居 for dx, dy in directions: nx, ny x dx, y dy if 0 nx M and 0 ny M: if not visited[nx][ny] and book[nx][ny] target: neighbors.append((nx, ny)) # 关键步骤按字典序排序邻居 (先比行再比列) neighbors.sort(keylambda p: (p[0], p[1])) for nx, ny in neighbors: visited[nx][ny] True path.append(nx) path.append(ny) if dfs(idx 1, nx, ny, path): return True # 回溯 path.pop() path.pop() visited[nx][ny] False return False # 1. 收集并排序所有起点 starts [] for i in range(M): for j in range(M): if book[i][j] data[0]: starts.append((i, j)) starts.sort(keylambda p: (p[0], p[1])) # 2. 依次尝试起点 found False for sx, sy in starts: visited[sx][sy] True current_path [sx, sy] if dfs(1, sx, sy, current_path): result_path current_path found True break visited[sx][sy] False # --- 输出 --- if found: print( .join(map(str, result_path))) else: print(error) if __name__ __main__: solve()2. JavaScript实现JS 需要注意异步输入流的读取以及数组的浅拷贝/回溯处理。const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); let lines []; let lineIndex 0; rl.on(line, (line) { lines.push(line.trim()); }); rl.on(close, () { // 扁平化所有输入 token const tokens lines.join( ).split(/\s/).filter(t t ! ); if (tokens.length 0) return; let idx 0; const N parseInt(tokens[idx]); const data []; for (let i 0; i N; i) { data.push(parseInt(tokens[idx])); } const M parseInt(tokens[idx]); const book []; for (let i 0; i M; i) { const row []; for (let j 0; j M; j) { row.push(parseInt(tokens[idx])); } book.push(row); } // 方向上下左右 const dirs [[-1, 0], [1, 0], [0, -1], [0, 1]]; const visited Array.from({ length: M }, () Array(M).fill(false)); let resultPath null; function dfs(currentIdx, x, y, path) { if (currentIdx N) { resultPath [...path]; return true; } const target data[currentIdx]; const neighbors []; for (const [dx, dy] of dirs) { const nx x dx; const ny y dy; if (nx 0 nx M ny 0 ny M) { if (!visited[nx][ny] book[nx][ny] target) { neighbors.push([nx, ny]); } } } // 排序邻居行优先列次之 neighbors.sort((a, b) { if (a[0] ! b[0]) return a[0] - b[0]; return a[1] - b[1]; }); for (const [nx, ny] of neighbors) { visited[nx][ny] true; path.push(nx, ny); if (dfs(currentIdx 1, nx, ny, path)) { return true; // 找到即返回 } // 回溯 path.pop(); path.pop(); visited[nx][ny] false; } return false; } // 收集起点 const starts []; for (let i 0; i M; i) { for (let j 0; j M; j) { if (book[i][j] data[0]) { starts.push([i, j]); } } } // 排序起点 starts.sort((a, b) { if (a[0] ! b[0]) return a[0] - b[0]; return a[1] - b[1]; }); let found false; for (const [sx, sy] of starts) { visited[sx][sy] true; const path [sx, sy]; if (dfs(1, sx, sy, path)) { found true; break; } visited[sx][sy] false; } if (found) { console.log(resultPath.join( )); } else { console.log(error); } });四、关键点解析与避坑1. 为什么不用比较所有路径很多初学者会写出“收集所有路径 -sort()- 取第一个”的代码。风险当 N200且矩阵中数字重复度高时路径数量可能达到天文数字内存溢出或超时。正解利用DFS 的贪心性质。只要我们在每一层递归都严格按照坐标从小到大遍历子节点第一条触达终点的路径必然是字典序最小的。这就像在字典里查单词按字母顺序找找到的第一个一定是排在前面的。2. 回溯的细节状态恢复在递归调用返回后无论成功与否只要不是直接向上返回成功必须将visited重置为false并将path中追加的坐标弹出。路径传递Python/JS 中列表/数组是引用传递。建议在递归参数中直接复用同一个列表通过push和pop维护状态避免每次递归都slice或copy数组这样能显著减少内存开销和时间消耗。3. 输入处理的陷阱多空格/换行测试用例中数字之间可能有多个空格或者换行不规范。Python:sys.stdin.read().split()会自动处理所有空白符空格、换行、制表符是最稳健的方式。JS:line.trim().split(/\s/)配合流式读取或者像示例中那样先合并再分割。边界检查矩阵坐标越界判断0 nx M必不可少。4. 特殊场景无解如果明文中的某个数字在矩阵中根本不存在或者虽然存在但无法形成连通路径循环结束后需输出error。单字符明文 N1 时只需找到字典序最小的那个数字的坐标即可代码逻辑天然支持dfs初始调用idx1直接命中终止条件。五、总结这道题是考察回溯算法与贪心思想结合的经典案例。核心技巧通过控制搜索顺序来替代结果排序。语言特性Python代码简洁sort和列表操作非常直观适合快速解题。JavaScript需注意异步 IO 处理和数组引用的回溯细节逻辑与 Python 高度一致。掌握这种“有序搜索 剪枝”的模式不仅能解决本题还能应用到许多类似的“求最小/最大路径”、“字典序排列”等图论搜索问题中。祝大家在机考中旗开得胜如有疑问欢迎评论区交流
