大厂算法：特殊的加密算法

一、题目

有一种特殊的加密算法，明文为一段数字串，经过密码本查找转换，生成另一段密文数字串。
规则如下：
1. 明文为一段数字串由 0\~9 组成
2. 密码本为数字 0\~9 组成的二维数组
3. 需要按明文串的数字顺序在密码本里找到同样的数字串，密码本里的数字串是由相邻的单元格数字组成，上下和左右是相邻的，注意：对角线不相邻，同一个单元格的数字不能重复使用。
4. 每一位明文对应密文即为密码本中找到的单元格
所在的行和列序号（序号从0开始）组成的两个数宇。
如明文第 i 位 Data[i] 对应密码本单元格为 Book[x][y]，
则明文第 i 位对应的密文为X Y，X和Y之间用空格隔开。
如果有多条密文，返回字符序最小的密文。
5. 如果密码本无法匹配，返回"error"。

二、输入

第一行输入 1 个正整数 N，代表明文的长度（1 ≤ N ≤ 200）
第二行输入 N 个明文组成的序列 Data[i]（0 ≤ Data[i] ≤ 9）
第三行输入 1 个正整数 M，代表密文的长度
接下来 M 行，每行 M 个数，代表密文矩阵

三、输出

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

四、示例

输入：
2
0 3
3
0 0 2
1 3 4
6 6 4

输出：
0 1 1 1

五、题解

1. 题意理解上比较重要，密码本里的数字串是由相邻的单元格数字组成，这是为啥有方向数组的原因
2. DFS 回溯实现过程中 visited 访问数组有选择和撤销。回溯实现中对同一个节点会存在多次试探访问
3. DFS 深度递归过程中为了避免传递太多参数，声明了类级别的全局变量，递归过程中直接更新

5.1 Java 实现

package org.stone.study.algo.ex202411;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 有一种特殊的加密算法，明文为一段数字串，经过密码本查找转换，生成另一段密文数字串。
 * 规则如下：
 * 1. 明文为一段数字串由 0\~9 组成
 * 2. 密码本为数字 0\~9 组成的二维数组
 * 3. 需要按明文串的数字顺序在密码本里找到同样的数字串，密码本里的数字串是由相邻的单元格数字组成，上下和左右是相邻的，注意：对角线不相邻，同一个单元格的数字不能重复使用。
 * 4. 每一位明文对应密文即为密码本中找到的单元格
 * 所在的行和列序号（序号从0开始）组成的两个数宇。
 * 如明文第 i 位 Data[i] 对应密码本单元格为 Book[x][y]，
 * 则明文第 i 位对应的密文为X Y，X和Y之间用空格隔开。
 * 如果有多条密文，返回字符序最小的密文。
 * 5. 如果密码本无法匹配，返回"error"。
 */
public class SpecialEncryption {
    private static int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private static String minPath;
    private static boolean found;
    private static int[][] book;
    private static int[] data;
    private static boolean[][] visited;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 2
        int n = scanner.nextInt();
        scanner.nextLine();
        // 0 3
        String[] strArr = scanner.nextLine().split(" ");
        data = Arrays.stream(strArr).mapToInt(Integer::parseInt).toArray();
        // 3
        int m = scanner.nextInt();
        scanner.nextLine();
        // 0 0 2
        // 1 3 4
        // 6 6 4
        book = new int[m][m];
        visited = new boolean[m][m];
        for(int i = 0; i < m; i++) {
            book[i] = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            Arrays.fill(visited[i], false);
        }

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < m; j++) {
                if(book[i][j] == data[0]) {
                    dfs(0, i, j, "");
                }
            }

        }
        // 0 1 1 1
        System.out.println(minPath);
    }

    /**
     * 深度递归回溯
     * @param index
     * @param i
     * @param j
     * @param path
     */
    private static void dfs(int index, int i, int j, String path) {
        int n = data.length;
        int m= book.length;

        if(index == n) {
            if(!found || path.length() < minPath.length()) {
                minPath = path;
            }

            found = true;
            return;
        }

        if(i < 0 || i >= m || j < 0 || j >= m || visited[i][j] || book[i][j] != data[index]) {
            return;
        }

        visited[i][j] = true;
        String newPath = path + i + " " + j + " ";
        for(int[] dir : dirs) {
            int x = i + dir[0];
            int y = j + dir[1];
            dfs(index + 1, x, y, newPath);
        }
        visited[i][j] = false;
    }
}

5.2 Python实现

dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
min_path = ''
found = False

# 深度优先搜索
def dfs(index, i, j, path):
    global found, min_path
    n = len(data)
    m = len(visited)

    if index == n:
        if not found or len(path) < len(min_path):
            min_path = path
        found = True
        return
    
    if i < 0 or i >= m or j < 0 or j >= m or visited[i][j] or book[i][j] != data[index]:
        return
    
    visited[i][j] = True
    # new_path是字符串（不变量，非全局），回溯时不需要撤销
    new_path = path + f'{i} {j} '
    for x, y in dirs:
        ni, nj = i + x, j + y
        dfs(index + 1, ni, nj, new_path)

    visited[i][j] = False

if __name__ == '__main__':
    # 初始化明文
    n = int(input())
    data = list(map(int, input().split()))
    # 初始化密码本
    m = int(input())
    book = [list(map(int, input().split())) for _ in range(m)]
    # 初始化访问数组, 回溯时会选择和撤销
    visited = [[False] * m for _ in range(m)]

    for i in range(m):
        for j in range(m):
            if book[i][j] == data[0]:
                dfs(0, i, j, '')

    print(min_path if found else 'Error')