一、题目 §
有一种特殊的加密算法，明文为一段数字串，经过密码本查找转换，生成另一段密文数字串。
规则如下：
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
五、题解 §
- 题意理解上比较重要，
密码本里的数字串是由相邻的单元格数字组成，这是为啥有方向数组的原因
- DFS 回溯实现过程中 visited 访问数组有选择和撤销。回溯实现中对同一个节点会存在多次试探访问
- 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')