18.华为OD-特殊的加密算法详解与Java实现（2024年OD D卷）

📋 题目概述

问题描述

特殊的加密算法要求我们在一个数字矩阵（密码本）中寻找一条路径，该路径上的数字序列与明文数字序列完全匹配。加密过程是将路径中每个单元格的坐标（行号和列号）按顺序输出，形成密文。

核心规则

1. 明文结构：由0-9数字组成的字符串，数字间可能有空格分隔

2. 密码本结构：0-9数字组成的二维数组

3. 路径约束：

   • 路径中相邻单元格必须是上下左右相邻（对角线不相邻）

   • 每个单元格只能使用一次

   • 路径上的数字序列必须与明文完全一致

4. 密文格式：每个数字对应两个坐标值（行 列），坐标值用空格分隔

5. 结果要求：如有多条密文，返回字符序最小的密文；如无法匹配，返回"error"

🎯 算法设计思路

问题本质分析

这是一个典型的图搜索问题，可以建模为：

• 节点：密码本中的每个单元格

• 边：相邻单元格之间的连接（上下左右）

• 目标：寻找一条路径，路径上的数字序列等于明文序列

解决方案：DFS + 回溯算法

核心算法流程

flowchart TD A[开始] --> B[读取密码本和明文] B --> C[预处理数据] C --> D{明文长度>0?} D -->|否| E[返回空字符串] D -->|是| F[寻找所有起点] F --> G[对每个起点进行DFS搜索] G --> H{找到完整路径?} H -->|是| I[保存路径] H -->|否| J[继续搜索] I --> K[所有路径搜索完成] J --> K K --> L{有找到路径?} L -->|否| M[返回"error"] L -->|是| N[按字典序排序路径] N --> O[选择最小字典序路径] O --> P[构建密文字符串] P --> Q[输出结果]

💻 Java代码实现

完整代码

package com.study.algorithm.HuaweiOD.特殊的加密算法; import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * 华为OD-特殊的加密算法 * 2024年OD（D卷）详解与Java实现 * * @author Tony_Yi * @date 2025/12/21 */ public class SpecialEncryption { // 四个方向：上、下、左、右 private static final int[][] DIRECTIONS = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}