[华为OD] C卷 dfs 特殊加密算法 100

题目：

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

规则如下

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:

密码本：

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：

输入：

0 3

0 0 2

1 3 4

6 6 4

输出：

0 1 1 1

示例2：

输入：

0 5

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;

    }

}

验证结果：