当前位置：首页 > news >正文

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

news 2026/8/23 21:33:09

一、题目

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

二、解题思路：为什么“第一个”就是“最小”？

本题的难点在于“字典序最小”。通常的思路是：找出所有路径 -> 转换为字符串 -> 排序 -> 取最小。
但在 N 高达 200 的情况下，路径数量可能是指数级的，全量搜索会导致TLE(超时)。

1、核心优化：贪心搜索顺序✅

字典序的比较是从左到右的。如果我们能保证在搜索的每一步，都优先尝试坐标值更小的选项，那么深度优先搜索（DFS）就是字典序最小的路径。

具体策略：

起点排序：遍历矩阵找到所有等于data[0]的点，按(行, 列)从小到大排序，依次作为起点尝试。
邻居排序：在 DFS 的每一步，收集所有合法的相邻点（值匹配且未访问），同样按(行, 列)从小到大排序。
早期终止：一旦某条路径成功匹配完整个明文序列，立即返回结果，不再搜索其他分支。

结论：无需存储所有路径，无需最后排序。搜索顺序即排序顺序。

2、算法流程

解析输入，构建矩阵。
收集所有可能的起点坐标，排序。
对每个起点执行DFS：
- 标记当前点已访问。
- 若已匹配完所有字符，记录路径并返回True。
- 否则，获取下一位明文所需的相邻点，排序后递归。
- 若递归返回True，直接向上返回True（剪枝）。
- 若递归失败，回溯（取消标记，弹出路径）。
若所有起点尝试完毕仍未找到，输出error。

三、代码实现💻

1. Python实现

Python 的列表推导式和递归非常适合此类问题。注意使用sys.stdin处理多行输入。

import sys # 增加递归深度，防止 N=200 时爆栈 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(key=lambda 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(key=lambda 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()-> 取第一个”的代码。

风险：当 N=200且矩阵中数字重复度高时，路径数量可能达到天文数字，内存溢出或超时。
正解：利用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必不可少。