🍭 大家好這里是清隆學長 ，一枚熱愛算法的程序員

? 本系列打算持續跟新華為OD-C/D卷的三語言AC題解

💻 ACM銀牌🥈| 多次AK大廠筆試 ｜ 編程一對一輔導

👏 感謝大家的訂閱? 和 喜歡💗

📎在線評測鏈接

https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1082

🌍 評測功能需要 ? 訂閱專欄 ? 后私信聯系清隆解鎖～

🍓OJ題目截圖

🥝 特殊加密算法

問題描述

有一種特殊的加密算法，明文為一段數字串，經過密碼本查找轉換，生成另一段密文數字串。規則如下：

1. 明文為一段由 0-9 組成的數字串。
2. 密碼本為由數字 0-9 組成的二維數組。
3. 需要按明文串的數字順序在密碼本里找到同樣的數字串，密碼本里的數字串是由相鄰的單元格數字組成，上下和左右是相鄰的，注意：對角線不相鄰，同一個單元格的數字不能重復使用。
4. 每一位明文對應密文即為密碼本中找到的單元格所在的行和列序號（序號從 0 開始）組成的兩個數字。如明文第 $i$ 位 $Data[i]$ 對應密碼本單元格為 $Book[x][y]$，則明文第 $i$ 位對應的密文為 $XY$，$X$ 和 $Y$ 之間用空格隔開。

如果有多條密文，返回字符序最小的密文。如果密碼本無法匹配，返回 “error”。

輸入格式

第一行輸入 1 個正整數 $N$，代表明文的長度 $(1\le N\le 200)$。

第二行輸入 $N$ 個明文數字組成的序列 $Data[i]$（整數：$0\le Data[i]\le 9$）。

第三行 1 個正整數 $M$，代表密文的長度。

接下來 $M$ 行，每行 $M$ 個數，代表密文矩陣。

輸出格式

輸出字典序最小密文。如果無法匹配，輸出 “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”。

數據范圍

• $1\le N\le 200$
• $0\le Data[i]\le 9$
• $1\le M\le 200$

題解

這道題的核心在于使用深度優先搜索（DFS）來遍歷密碼本，尋找符合條件的路徑。需要從每一個可能的起點開始搜索，并記錄路徑。如果找到多條路徑，選擇字典序最小的那條。

參考代碼

• Python

import sysdef dfs(x, y, k, visited, result):visited[x][y] = Trueresult.append(x)result.append(y)if k == n - 1:return Truefor 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 Truevisited[x][y] = Falseresult.pop()result.pop()return Falsen = 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();}m = sc.nextInt();matrix = new int[m][m];for (int i = 0; i < m; i++) {for (int j = 0; j < m; j++) {matrix[i][j] = sc.nextInt();}}for (int i = 0; i < m; i++) {for (int j = 0; j < m; j++) {if (matrix[i][j] == data[0]) {boolean[][] visited = new boolean[m][m];List<Integer> result = new ArrayList<>();if (dfs(i, j, 0, visited, result)) {for (int k = 0; k < result.size(); k++) {System.out.print(result.get(k));if (k < result.size() - 1) {System.out.print(" ");}}return;}}}}System.out.println("error");}static boolean dfs(int x, int y, int k, boolean[][] visited, List<Integer> result) {visited[x][y] = true;result.add(x);result.add(y);if (k == n - 1) {return true;}for (int idx = 0; idx < 4; idx++) {int nx = x + dx[idx];int ny = y + dy[idx];if (nx >= 0 && nx < m && ny >= 0 && ny < m && !visited[nx][ny] && matrix[nx][ny] == data[k + 1]) {if (dfs(nx, ny, k + 1, visited, result)) {return true;}}}visited[x][y] = false;result.remove(result.size() - 1);result.remove(result.size() - 1);return false;}
}

• Cpp

#include <bits/stdc++.h>using namespace std;int n, m;
vector<int> plaintext;
vector<vector<int>> matrix;
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};bool dfs(int x, int y, int k, vector<vector<int>>& visited, vector<int>& result) {visited[x][y] = 1;result.push_back(x);result.push_back(y);if (k == n - 1) {return true;}for (int idx = 0; idx < 4; idx++) {int nx = x + dx[idx];int ny = y + dy[idx];if (nx >= 0 && nx < m && ny >= 0 && ny < m && !visited[nx][ny] && matrix[nx][ny] == plaintext[k + 1]) {if (dfs(nx, ny, k + 1, visited, result)) {return true;}}}visited[x][y] = 0;result.pop_back();result.pop_back();return false;
}int main() {cin >> n;plaintext.resize(n);for (int i = 0; i < n; i++) {cin >> plaintext[i];}cin >> m;matrix.resize(m, vector<int>(m));for (int i = 0; i < m; i++) {for (int j = 0; j < m; j++) {cin >> matrix[i][j];}}for (int i = 0; i < m; i++) {for (int j = 0; j < m; j++) {if (matrix[i][j] == plaintext[0]) {vector<vector<int>> visited(m, vector<int>(m, 0));vector<int> result;if (dfs(i, j, 0, visited, result)) {for (int k = 0; k < result.size(); k++) {cout << result[k];if (k < result.size() - 1) {cout << " ";}}return 0;}}}}cout << "error" << endl;return 0;
}