题目：
有一种特殊的加密算法，明文为一段数字串，经过密码本查找转换，生成另一段密文数字串。
规则如下
1•明文为一段数字串由0-9组成
2.密码本为数字0-9组成的二维数组
3•需要按明文串的数字顺序在密码本里找到同样的数字串，密码本里的数字串是由相邻的单元
格数字组成，上下和左右是相邻的，注意:对角线不相邻，同一个单元格的数字不能重复使
用。
4 •每一位明文对应密文即为密码本中找到的单元格所在的行和列序号（序号从0开始）组成的两个
数字。如明文第位Data[i]对应密码本单元格为Book[x][y],则明文第i位对应的密文为XY, X和
Y之间用空格隔开
如果有多条密文，返回字符序最小的密文。如果密码本无法匹配，返回"error"
请你设计这个加密程序
示例1：
密码本
[0 0 2]
[1 3 4]
[6 6 4]
明文：3,密文."1 1”
示例2:
示例2:
密码本：
0 0 2
1 3 4
6 6 4
明文:"0 3”密文:0 1 1 1”
输入描述
第一行输入1个正整数N,代表明文的长度(1 <= N <= 200)
第二行输入N个明文数字组成的序列Data[i](整数：0<= Data[i] <= 9)
第三行1个正整数M,代表密文的长度接下来M行，每行M个数，代表密文矩阵
输出描述
输出字典序最小密文•如果无法匹配，输出"error
示例1：
输入：
2
0 3
3
0 0 2
1 3 4
6 6 4
输出：
0 1 1 1
示例2：
输入：
2
0 5
3
0 0 2
1 3 4
6 6 4
输出：
error
题解：
要在矩阵中找到连续的坐标位置，那么这种搜索就直接使用DFS搜索算法。这个题要注意有多条密文时候返回字符序最小的密文。所有搜索的时候顺序应该是左->上->下->右（因为排列是先x坐标后y坐标），这样找到第一个符合条件的数据就是最小的密文。
如果不按这个顺序的话，那么就需要将多条密文序列进行排序，找出最小结果了（这个逻辑比较好理解）
这个题只有100分，但感觉还是有点难度的
代码
import java.util.*;
public class DFS1 {
private static String result = "";
// private static String sumResult = "";
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = Integer.valueOf(sc.nextLine());
String nums[] =sc.nextLine().split(" ");
int value[] = new int[num];
for(int i =0;i<nums.length;i++){
value[i] = Integer.valueOf(nums[i]);
}
int m = Integer.valueOf(sc.nextLine());
int arr[][] = new int[m][m];
for(int i=0;i<m;i++){
String arrs[] = sc.nextLine().split(" ");
for(int j =0;j<m;j++){
arr[i][j] = Integer.valueOf(arrs[j]);
}
}
int directions[][] = {{-1,0},{0,-1},{0,1},{1,0}}; // 搜索顺序 很重要,这样第一个结果就是最小值了
boolean hasdata = false;
// Map<String,List<String>> resultMap = new HashMap<>();
// List<String> resultValues = new ArrayList<>();
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
if(arr[i][j] == value[0]){
result = i+" "+j;
// sumResult = String.valueOf(i)+String.valueOf(j);
// System.out.println("first is i"+i+"j "+j);
if(dfs(directions,arr,i,j,value,1,m)){
hasdata = true;
// List<String> stringList = new ArrayList<>();
// stringList.add(result);
// resultMap.put(sumResult,stringList);
// resultValues.add(sumResult);
break;
}
}
}
if(hasdata){
break;
}
}
if(hasdata){
// Collections.sort(resultValues);
// System.out.println(resultMap.get(resultValues.get(0)).get(0));
System.out.println(result);
}
else {
System.out.println("error");
}
}
public static boolean dfs(int[][] directions, int[][] arrs, int x, int y, int[] value, int index, int m) {
int presentValue = value[index];
int i = 0;
while (i < 4) {
if(i>=4){
break;
}
int newX = x + directions[i][0];
int newY = y + directions[i][1];
// if (newX >= 0 && newX < m && newY >= 0 && newY < m) {
// System.out.println("newX " + newX + " newY " + newY + " arrs[newX][newY " + arrs[newX][newY] + "presentValue " + presentValue);
// }
if (newX >= 0 && newX < m && newY >= 0 && newY < m && arrs[newX][newY] == presentValue) {
result += " " + newX + " " + newY;
// sumResult = sumResult + String.valueOf(newX) + String.valueOf(newY);
if (index == value.length - 1) {
return true;
}
index++;
return dfs(directions, arrs, newX, newY, value, index, m);
}
if (newX < 0 || newX >= m || newY < 0 || newY >= m || arrs[newX][newY] != presentValue) {
i++;
continue;
}
}
return false;
}
}
方法2：不考虑搜索顺序，按照结果集排序，找出最小的
import java.util.*;
public class DFS1 {
private static String result = "";
private static String sumResult = "";
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = Integer.valueOf(sc.nextLine());
String nums[] =sc.nextLine().split(" ");
int value[] = new int[num];
for(int i =0;i<nums.length;i++){
value[i] = Integer.valueOf(nums[i]);
}
int m = Integer.valueOf(sc.nextLine());
int arr[][] = new int[m][m];
for(int i=0;i<m;i++){
String arrs[] = sc.nextLine().split(" ");
for(int j =0;j<m;j++){
arr[i][j] = Integer.valueOf(arrs[j]);
}
}
// int directions[][] = {{-1,0},{0,-1},{0,1},{1,0}}; // 搜索顺序 很重要,这样第一个结果就是最小值了
int directions[][] = {{-1,0},{0,-1},{1,0},{0,1}}; // 搜索顺序 很重要,这样第一个结果就是最小值了
boolean hasdata = false;
Map<String,List<String>> resultMap = new HashMap<>();
List<String> resultValues = new ArrayList<>();
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
if(arr[i][j] == value[0]){
result = i+" "+j;
sumResult = String.valueOf(i)+String.valueOf(j);
// System.out.println("first is i"+i+"j "+j);
if(dfs(directions,arr,i,j,value,1,m)){
hasdata = true;
List<String> stringList = new ArrayList<>();
stringList.add(result);
resultMap.put(sumResult,stringList);
resultValues.add(sumResult);
break;
}
}
}
// if(hasdata){
// break;
// }
}
if(hasdata){
Collections.sort(resultValues);
System.out.println(resultMap.get(resultValues.get(0)).get(0));
// System.out.println(result);
}
else {
System.out.println("error");
}
}
public static boolean dfs(int[][] directions, int[][] arrs, int x, int y, int[] value, int index, int m) {
int presentValue = value[index];
int i = 0;
while (i < 4) {
if(i>=4){
break;
}
int newX = x + directions[i][0];
int newY = y + directions[i][1];
// if (newX >= 0 && newX < m && newY >= 0 && newY < m) {
// System.out.println("newX " + newX + " newY " + newY + " arrs[newX][newY " + arrs[newX][newY] + "presentValue " + presentValue);
// }
if (newX >= 0 && newX < m && newY >= 0 && newY < m && arrs[newX][newY] == presentValue) {
result += " " + newX + " " + newY;
sumResult = sumResult + String.valueOf(newX) + String.valueOf(newY);
if (index == value.length - 1) {
return true;
}
index++;
return dfs(directions, arrs, newX, newY, value, index, m);
}
if (newX < 0 || newX >= m || newY < 0 || newY >= m || arrs[newX][newY] != presentValue) {
i++;
continue;
}
}
return false;
}
}
验证结果：
