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

📋 题目概述

问题描述

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

核心规则

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

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

路径约束：

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

每个单元格只能使用一次

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

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

结果要求：如有多条密文，返回字符序最小的密文；如无法匹配，返回”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}};
    
    public static void main(String[] args) {
        // 读取密码本
        Scanner scanner = new Scanner(System.in);
        List<int[]> bookList = new ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (line.isEmpty()) {
                break;
            }
            String[] parts = line.split("\s+");
            int[] row = new int[parts.length];
            for (int i = 0; i < parts.length; i++) {
                row[i] = Integer.parseInt(parts[i]);
            }
            bookList.add(row);
        }
 
        // 密码本转化为二维数组
        int rows = bookList.size();
        int cols = bookList.get(0).length;
        int[][] book = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            book[i] = bookList.get(i);
        }
 
        // 读取明文
        String plainText = scanner.nextLine().trim();
        String[] plainDigits = plainText.split("\s+");
        int[] plain = new int[plainDigits.length];
        for (int i = 0; i < plainDigits.length; i++) {
            plain[i] = Integer.parseInt(plainDigits[i]);
        }
 
        // 执行加密算法
        String result = encrypt(book, plain);
        System.out.println(result);
        scanner.close();
    }
    
    /**
     * 加密主函数
     * 
     * @param book 密码本二维数组
     * @param plain 明文数字数组
     * @return 加密结果字符串
     */
    private static String encrypt(int[][] book, int[] plain) {
        if (plain.length == 0) {
            return "";
        }
        
        int rows = book.length;
        int cols = book[0].length;
        
        // 存储所有可能的路径
        List<List<int[]>> allPaths = new ArrayList<>();
        
        // 找到所有可能的起点（第一个数字匹配的位置）
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (book[i][j] == plain[0]) {
                    boolean[][] visited = new boolean[rows][cols];
                    visited[i][j] = true;
                    List<int[]> path = new ArrayList<>();
                    path.add(new int[]{i, j});
                    dfs(book, plain, i, j, 1, visited, path, allPaths);
                }
            }
        }
        
        // 如果没有找到任何路径
        if (allPaths.isEmpty()) {
            return "error";
        }
        
        // 按字典序排序所有路径
        allPaths.sort((path1, path2) -> {
            for (int i = 0; i < Math.min(path1.size(), path2.size()); i++) {
                int[] coord1 = path1.get(i);
                int[] coord2 = path2.get(i);
                if (coord1[0] != coord2[0]) {
                    return Integer.compare(coord1[0], coord2[0]);
                }
                if (coord1[1] != coord2[1]) {
                    return Integer.compare(coord1[1], coord2[1]);
                }
            }
            return Integer.compare(path1.size(), path2.size());
        });
        
        // 构建结果字符串
        return buildResult(allPaths.get(0));
    }
    
    /**
     * 深度优先搜索（DFS）递归函数
     * 
     * @param book 密码本
     * @param plain 明文数字序列
     * @param x 当前行坐标
     * @param y 当前列坐标
     * @param index 当前匹配的明文索引
     * @param visited 访问标记数组
     * @param currentPath 当前路径
     * @param allPaths 所有找到的路径
     */
    private static void dfs(int[][] book, int[] plain, int x, int y, int index, 
                           boolean[][] visited, List<int[]> currentPath, 
                           List<List<int[]>> allPaths) {
        // 如果已经匹配完所有明文数字
        if (index == plain.length) {
            allPaths.add(new ArrayList<>(currentPath));
            return;
        }
        
        // 尝试四个方向
        for (int[] dir : DIRECTIONS) {
            int newX = x + dir[0];
            int newY = y + dir[1];
            
            // 检查边界和访问状态
            if (newX >= 0 && newX < book.length && 
                newY >= 0 && newY < book[0].length && 
                !visited[newX][newY] && 
                book[newX][newY] == plain[index]) {
                
                // 标记已访问
                visited[newX][newY] = true;
                currentPath.add(new int[]{newX, newY});
                
                // 继续搜索
                dfs(book, plain, newX, newY, index + 1, visited, currentPath, allPaths);
                
                // 回溯：恢复状态
                currentPath.remove(currentPath.size() - 1);
                visited[newX][newY] = false;
            }
        }
    }
    
    /**
     * 构建结果字符串
     * 
     * @param path 路径坐标列表
     * @return 格式化后的密文字符串
     */
    private static String buildResult(List<int[]> path) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < path.size(); i++) {
            int[] coord = path.get(i);
            sb.append(coord[0]).append(" ").append(coord[1]);
            if (i < path.size() - 1) {
                sb.append(" ");
            }
        }
        return sb.toString();
    }
}

测试用例演示

测试用例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

测试用例3：复杂路径

// 输入：
// 1 2 3
// 4 5 6
// 7 8 9
//
// 1 2 3 6 5 4 7 8 9
//
// 输出：0 0 0 1 0 2 1 2 1 1 1 0 2 0 2 1 2 2

📊 算法复杂度分析

时间复杂度

最坏情况：O(rows × cols × 4^L)

rows, cols：密码本的行数和列数

L：明文长度

4^L：每个位置最多有4个方向可选

优化因素：

剪枝：数字不匹配时立即返回

起点筛选：只从与明文第一个数字匹配的位置开始搜索

访问标记：避免重复使用单元格

空间复杂度

主要消耗：

visited数组：O(rows × cols)

递归栈：O(L)

路径存储：O(L)

🔧 关键技术与优化

1. 深度优先搜索（DFS）策略

DFS适合寻找所有可能路径的场景，通过递归遍历所有可能的路径组合。

2. 回溯算法机制

回溯是DFS的核心，确保在探索失败时能够返回上一步继续尝试其他方向。

3. 字典序排序技巧

使用自定义比较器对路径进行排序，确保选择最小字典序的结果。

4. 剪枝优化

数字匹配剪枝：当前位置数字与明文不匹配时立即返回

边界检查：确保不越界访问

访问标记：避免重复使用单元格

❓ 常见问题与解答

Q1: 如果有多个相同数字的起点，如何选择？

A：算法会从所有匹配的起点开始搜索，收集所有完整路径，然后按字典序排序选择最小的。

Q2: 如何保证不重复使用单元格？

A：使用boolean类型的visited数组标记已访问的单元格，在DFS过程中维护访问状态。

Q3: 字典序比较的具体规则是什么？

A：比较两个路径的坐标序列：

先比较第一个坐标的行号，小的在前

行号相同比较列号，小的在前

依次比较后续坐标

Q4: 如果明文为空如何处理？

A：根据题目要求，明文非空。如果为空，可以返回空字符串或”error”。

Q5: 如何处理密码本输入格式？

A：使用Scanner逐行读取，遇到空行表示密码本输入结束，下一行开始是明文。

🔄 扩展与变体

变体1：允许对角线移动

如果允许对角线移动，只需修改DIRECTIONS数组包含8个方向即可。

变体2：允许重复使用单元格

如果允许重复使用单元格，只需去掉visited数组的限制即可。

变体3：最短路径优先

如果要求最短路径，可以将DFS改为BFS，或者使用A*算法。

📝 总结

本题考察了图搜索、深度优先搜索、回溯算法和字符串处理等多个知识点。通过DFS+回溯的经典组合，可以有效地解决在二维网格中寻找特定数字序列路径的问题。

核心要点：

理解题意，明确约束条件

合理设计DFS函数和状态管理

正确处理边界条件和回溯

实现正确的字典序比较逻辑

这种类型的题目在华为OD考试中较为常见，掌握DFS+回溯的解题模板对于解决类似问题非常有帮助。