E卷-刷题笔记合集🔗

特殊的加密算法

问题描述

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

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

样例输出1

0 1 1 1

样例输入2

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

样例输出2

error

数据范围

题解

DFS

这道题目本质上是一个路径搜索问题，使用深度优先搜索（DFS）来解决。主要思路如下：

1. 首先，遍历密码本矩阵，找到所有与明文第一个数字相匹配的位置作为起点。

2. 从每个起点开始，使用 DFS 搜索可能的路径。在搜索过程中，需要记录已经访问过的位置，避免重复使用。

3. 搜索时，每次向四个方向（上、下、左、右）尝试，如果下一个位置的数字与明文中的下一个数字匹配，就继续搜索。

4. 如果找到一条完整的路径（长度等于明文长度），就立即返回这条路径。由于我们是按照上、左、右、下的顺序搜索，第一条找到的路径就是字典序最小的路径。

5. 如果遍历完所有可能的起点都没有找到有效路径，则输出 "error"。

参考代码

• Python

import sys

def dfs(x, y, k, visited, result):
    # 将当前位置标记为已访问
    visited[x][y] = True
    # 将当前位置的坐标添加到结果中
    result.append(x)
    result.append(y)
    
    # 如果已经匹配了所有明文数字，返回True
    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]:
            # 如果找到了匹配的路径，返回True
            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()

# 如果遍历完整个矩阵都没有找到有效路径，输出"error"
print("error")

• C

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define MAX_N 200
#define MAX_M 200

int n, m;
int data[MAX_N];
int matrix[MAX_M][MAX_M];
bool visited[MAX_M][MAX_M];
int result[MAX_N * 2];
// 定义四个方向的偏移量：上、左、右、下
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};

bool dfs(int x, int y, int k) {
    // 将当前位置标记为已访问
    visited[x][y] = true;
    // 将当前位置的坐标添加到结果中
    result[k * 2] = x;
    result[k * 2 + 1] = y;

    // 如果已经匹配了所有明文数字，返回true
    if (k == n - 1) return true;

    // 向四个方向搜索
    for (int idx = 0; idx < 4; idx++) {
        int nx = x + dx[idx];
        int ny = y + dy[idx];
        // 检查新位置是否在矩阵范围内，是否未访问过，以及是否匹配下一个明文数字
        if (0 <= nx && nx < m && 0 <= ny && ny < m && !visited[nx][ny] && matrix[nx][ny] == data[k + 1]) {
            // 如果找到了匹配的路径，返回true
            if (dfs(nx, ny, k + 1)) return true;
        }
    }

    // 如果没有找到匹配，回溯
    visited[x][y] = false;
    return false;
}

int main() {
    // 读取输入
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &data[i]);
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &matrix[i][j]);

    // 遍历矩阵，寻找可能的起点
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            // 如果找到与第一个明文数字匹配的位置
            if (matrix[i