一、题目

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

1.明文为一段数字串由0-9组成。
2.密码本为数字0-9组成的二维数组。
3.需要按明文串的数字顺序在密码本里找到同样的数字串，密码本里的数字串是由相邻的单元格数字组成，上下和左右是相邻的，注意对角线不相邻，同一个单元格的数字不能重复使用。
4.每一位明文对应密文即为密码本中找到的单元格所在的行和列序号(序号从0开始)组成的两个数字。如明文第位Data[i]对应密码本单元格为Book[x][y]，则明文第位对应的密文为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：
输入：
2
0 3
3
0 0 2
1 3 4
6 6 4

输出：
0 1 1 1

示例2：
输入：

 5

 0 2
 3 4
 6 4
输出：
error

二、解题思路深度解析💡

本题本质上是一个带约束的深度优先搜索（DFS）问题，核心难点在于“字典序最小”的要求。

1. 核心算法：回溯 + 剪枝

我们需要遍历所有可能的起点，尝试构建长度为 N 的路径。

• 状态定义：dfs(index, x, y, path)
  • index: 当前匹配到明文的第几位。
  • x, y: 当前在矩阵中的坐标。
  • path: 当前已生成的密文序列（列表形式）。
• 终止条件：
  • index == N：找到一条完整路径，将其与当前全局最优解比较，更新最优解。
  • 无路可走：回溯。

2. 字典序最小的优化策略

直接搜索所有路径再排序会导致超时（ N 最大为 200，路径组合爆炸）。必须在搜索过程中进行贪心剪枝：

策略 A：起点的选择

• 收集所有等于 Data[0] 的坐标，按 (行号, 列号) 从小到大排序。
• 优先搜索行号小、列号小的起点。

策略 B：下一步的方向选择（关键）

• 在每一步扩展时，获取所有合法的相邻节点（值匹配且未访问）。
• 将这些候选节点按 (行号, 列号) 从小到大排序。
• 优先搜索坐标更小的节点。
• 剪枝优化：
  • 如果我们已经找到了一个完整解 bestPath。
  • 在当前搜索分支中，如果当前生成的局部路径 currentPath 的字典序已经大于 bestPath 的前缀，则可以直接剪枝（因为后续无论怎么选，整体字典序只会更大或相等，不会更小）。
  • 注：由于我们是按坐标从小到大搜索的，第一条找到的完整路径往往就是字典序最小的。
  • 结论：只要按照严格的坐标升序进行 DFS，第一个成功匹配到终点的路径即为答案，无需遍历所有路径，找到即可直接返回！这将复杂度从指数级大幅降低。

3. 数据结构设计

• 访问标记：使用 boolean[][] visited 记录路径中已使用的单元格，回溯时需还原。
• 结果存储：使用 List<Integer> 或切片存储坐标序列。

---

三、代码实现💻

1. Java 实现

利用 ArrayList 动态存储路径，通过递归顺序保证字典序最小。

import java.util.*;

public class Main {
    static int N, M;
    static int[] data;
    static int[][] book;
    static boolean[][] visited;
    static List<Integer> result = null; // 存储最终结果

    // 方向数组：上、下、左、右 (为了字典序最小，我们需要自定义遍历顺序)
    // 但更优的做法是动态收集邻居并排序，而不是固定方向顺序，因为(0,1)可能比(1,0)小，也可能大
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (!sc.hasNext()) return;

        N = sc.nextInt();
        data = new int[N];
        for (int i = 0; i < N; i++) data[i] = sc.nextInt();

        M = sc.nextInt();
        book = new int[M][M];
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < M; j++) {
                book[i][j] = sc.nextInt();
            }
        }

        // 1. 收集所有可能的起点 (值为 data[0])
        List<int[]> starts = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < M; j++) {
                if (book[i][j] == data[0]) {
                    starts.add(new int[]{i, j});
                }
            }
        }

        // 2. 起点按字典序排序 (行优先，列次之)
        starts.sort((a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            return a[1] - b[1];
        });

        visited = new boolean[M][M];

        // 3. 依次尝试每个起点，找到第一个成功的路径即为答案
        for (int[] start : starts) {
            visited[start[0]][start[1]] = true;
            List<Integer> path = new ArrayList<>();
            path.add(start[0]);
            path.add(start[1]);

            if (dfs(1, start[0], start[1], path)) {
                // 找到最优解，输出
                printResult(result);
                return;
            }

            // 回溯
            visited[start[0]][start[1]] = false;
        }

        System.out.println("error");
    }

    /**
     * @param index 当前匹配明文的索引
     * @param x 当前行
     * @param y 当前列
     * @param path 当前路径
     * @return 是否找到解
     */
    private static boolean dfs(int index, int x, int y, List<Integer> path) {
        if (index == N) {
            result = new ArrayList<>(path);
            return true;
        }

        int target = data[index];
        List<int[]> neighbors = new ArrayList<>();

        // 收集所有合法的邻居
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < M && ny >= 0 && ny < M 
                && !visited[nx][ny] && book[nx][ny] == target) {
                neighbors.add(new int[]{nx, ny});
            }
        }

        // 关键：对邻居排序，保证优先搜索字典序小的坐标
        neighbors.sort((a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            return a[1] - b[1];
        });

        // 按排序后的顺序尝试
        for (int[] next : neighbors) {
            int nx = next[0];
            int ny = next[1];
            
            visited[nx][ny] = true;
            path.add(nx);
            path.add(ny);

            if (dfs(index + 1, nx, ny, path)) {
                return true; // 一旦找到，立即返回，因为是按字典序搜索的
            }

            // 回溯
            path.remove(path.size() - 1);
            path.remove(path.size() - 1);
            visited[nx][ny] = false;
        }

        return false;
    }

    private static void printResult(List<Integer> res) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < res.size(); i++) {
            sb.append(res.get(i));
            if (i < res.size() - 1) sb.append(" ");
        }
        System.out.println(sb.toString());
    }
}

2. Go 实现

Go 语言在处理递归和切片时非常高效，适合此类搜索问题。

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

var (
	N, M    int
	data    []int
	book    [][]int
	visited [][]bool
	result  []int
	found   bool
)

type Point struct {
	x, y int
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	
	// 读取 N
	if !scanner.Scan() { return }
	N, _ = strconv.Atoi(strings.TrimSpace(scanner.Text()))

	// 读取明文
	if !scanner.Scan() { return }
	parts := strings.Fields(scanner.Text())
	data = make([]int, N)
	for i, s := range parts {
		data[i], _ = strconv.Atoi(s)
	}

	// 读取 M
	if !scanner.Scan() { return }
	M, _ = strconv.Atoi(strings.TrimSpace(scanner.Text()))

	// 读取矩阵
	book = make([][]int, M)
	visited = make([][]bool, M)
	for i := 0; i < M; i++ {
		book[i] = make([]int, M)
		visited[i] = make([]bool, M)
		if scanner.Scan() {
			rowParts := strings.Fields(scanner.Text())
			for j, s := range rowParts {
				book[i][j], _ = strconv.Atoi(s)
			}
		}
	}

	// 收集起点
	var starts []Point
	for i := 0; i < M; i++ {
		for j := 0; j < M; j++ {
			if book[i][j] == data[0] {
				starts = append(starts, Point{i, j})
			}
		}
	}

	// 排序起点
	sort.Slice(starts, func(i, j int) bool {
		if starts[i].x != starts[j].x {
			return starts[i].x < starts[j].x
		}
		return starts[i].y < starts[j].y
	})

	found = false
	result = nil

	// 尝试每个起点
	for _, start := range starts {
		path := make([]int, 0, N*2)
		path = append(path, start.x, start.y)
		visited[start.x][start.y] = true

		dfs(1, start.x, start.y, path)

		visited[start.x][start.y] = false
		if found {
			break
		}
	}

	if found {
		var out strings.Builder
		for i, v := range result {
			out.WriteString(strconv.Itoa(v))
			if i < len(result)-1 {
				out.WriteString(" ")
			}
		}
		fmt.Println(out.String())
	} else {
		fmt.Println("error")
	}
}

func dfs(index, x, y int, path []int) {
	if found { return // 剪枝：如果已经找到最优解，停止所有搜索
	}

	if index == N {
		result = make([]int, len(path))
		copy(result, path)
		found = true
		return
	}

	target := data[index]
	var neighbors []Point
	
	// 四个方向
	dirs := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
	for _, d := range dirs {
		nx, ny := x+d[0], y+d[1]
		if nx >= 0 && nx < M && ny >= 0 && ny < M && !visited[nx][ny] && book[nx][ny] == target {
			neighbors = append(neighbors, Point{nx, ny})
		}
	}

	// 排序邻居，保证字典序
	sort.Slice(neighbors, func(i, j int) bool {
		if neighbors[i].x != neighbors[j].x {
			return neighbors[i].x < neighbors[j].x
		}
		return neighbors[i].y < neighbors[j].y
	})

	for _, p := range neighbors {
		visited[p.x][p.y] = true
		newPath := append(path, p.x, p.y) // 创建新切片避免引用问题，或者手动回溯
		
		// 优化：复用 path 切片，手动回溯以减少内存分配
		// 这里为了逻辑清晰使用追加，实际竞赛中可优化为：
		// path = append(path, p.x, p.y); dfs(...); path = path[:len(path)-2]
		
		// 采用手动回溯优化版：
		// 注意：上面的 newPath 写法会复制切片，稍慢但安全。
		// 下面改用原地修改+回溯：
	}
	
	// 重写循环以使用原地回溯优化性能
	for _, p := range neighbors {
		visited[p.x][p.y] = true
		path = append(path, p.x, p.y)
		
		dfs(index+1, p.x, p.y, path)
		
		path = path[:len(path)-2] // 回溯
		visited[p.x][p.y] = false
		
		if found { return }
	}
}

---

四、关键点与避坑指南🔍

1. 为什么“第一个找到的解”就是最优解？

这是本题的核心优化点。

• 字典序的比较规则是：从左到右依次比较，一旦某一位不同，数值小的整个序列就小。
• 我们的搜索策略：
  1. 起点按 (x,y) 升序遍历。
  2. 每一步的邻居按 (x,y)升序遍历。
• 这意味着，我们总是优先尝试坐标值最小的路径分支。因此，深度优先搜索（DFS）找到的第一条完整路径，其每一位坐标都是在当前约束下能取到的最小值，必然是全局字典序最小的。
• 收益：无需保存所有路径进行比较，找到即 return，极大提升效率。

2. 数据范围与类型

• N≤200 ，路径长度为 2N=400 个整数。
• 矩阵 MM 未明确给出上限，但通常机考中 M≤50 或 100 。
• 时间复杂度：最坏情况 O(4N) ，但在强剪枝（找到即停）和网格限制下，实际运行非常快。

3. 输入处理细节

• 空格处理：输入的数字之间可能有多个空格，使用 scanner.Tokenize (Go) 或 split (Java) 时需兼容空白符。
• 换行符：读取整数后注意消耗换行符，防止读取字符串行时出错。

4. 常见错误

• 忘记回溯：visited 数组在递归返回前必须重置为 false，否则会影响其他分支的搜索。
• 方向不全：题目明确“上下左右”，不要包含对角线。
• 输出格式：数字之间必须有空格，行末通常不建议有多余空格（虽然部分OJ宽容，但最好严格处理）。

---

五、总结🎯

这道题是典型的图搜索 + 贪心策略问题。

• Java 选手注意 ArrayList 的回溯操作（remove lastIndex），以及对象引用的拷贝问题。
• Go 选手注意切片的扩容机制，推荐使用 append 配合切片截断 path[:len-2] 来避免频繁的内存分配。
• 通用技巧：利用搜索顺序的天然单调性来替代显式的排序比较，是解决“字典序最小/最大”类搜索题的金钥匙。

掌握这种“有序搜索 + 早期终止”的模式，能让你在面对类似的机考题目时游刃有余！

觉得有用？欢迎点赞、收藏、关注，获取更多华为OD机试全语言题解！