最新华为OD机试真题-特殊加密算法(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测

最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users

📎在线评测链接

特殊加密算法(200分)

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🥝 特殊加密算法

问题描述

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

1. 明文为一段由 0-9 组成的数字串。
2. 密码本为由数字 0-9 组成的二维数组。
3. 需要按明文串的数字顺序在密码本里找到同样的数字串，密码本里的数字串是由相邻的单元格数字组成，上下和左右是相邻的，注意：对角线不相邻，同一个单元格的数字不能重复使用。
4. 每一位明文对应密文即为密码本中找到的单元格所在的行和列序号（序号从 0 开始）组成的两个数字。如明文第 位 对应密码本单元格为 ，则明文第 位对应的密文为 ， 和 之间用空格隔开。

如果有多条密文，返回字符序最小的密文。如果密码本无法匹配，返回 "error"。

输入格式

第一行输入 1 个正整数 ，代表明文的长度 。

第二行输入 个明文数字组成的序列 （整数：）。

第三行 1 个正整数 ，代表密文的长度。

接下来 行，每行 个数，代表密文矩阵。

输出格式

输出字典序最小密文。如果无法匹配，输出 "error"。

样例输入

输入 1

2
0 3
3
0 0 2
1 3 4
6 6 4

输入 2

2
0 5
3
0 0 2
1 3 4
6 6 4

样例输出

输出 1

0 1 1 1

输出 2

error

样例解释

样例 1 中，明文 "0 3" 可以在密码本中找到对应的路径，且字典序最小的密文为 "0 1 1 1"。

样例 2 中，明文 "0 5" 无法在密码本中找到对应的路径，因此输出 "error"。

数据范围

题解

这道题的核心在于使用深度优先搜索（DFS）来遍历密码本，寻找符合条件的路径。需要从每一个可能的起点开始搜索，并记录路径。如果找到多条路径，选择字典序最小的那条。

参考代码

• Python

import sys

def dfs(x, y, k, visited, result):
    visited[x][y] = True
    result.append(x)
    result.append(y)
    if k == n - 1:
        return True

    for idx in range(4):
        nx = x + dx[idx]
        ny = y + dy[idx]
        if 0 <= nx < m and 0 <= ny < m and not visited[nx][ny] and matrix[nx][ny] == data[k + 1]:
            if dfs(nx, ny, k + 1, visited, result):
                return True

    visited[x][y] = False
    result.pop()
    result.pop()
    return False

n = int(input())
data = list(map(int, input().split()))
m = int(input())
matrix = [list(map(int, input().split())) for _ in range(m)]
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

for i in range(m):
    for j in range(m):
        if matrix[i][j] == data[0]:
            visited = [[False] * m for _ in range(m)]
            result = []
            if dfs(i, j, 0, visited, result):
                print(' '.join(map(str, result)))
                sys.exit()

print("error")

• Java

import java.util.*;

public class Main {
    static int n, m;
    static int[] data;
    static int[][] matrix;
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = sc.nextInt();
        }