P3809. 加密算法

解题思路

注意，本题和 经典题型. 单词搜索、【回溯】2023C-找到它 非常类似。唯一的区别是，题目不保证答案是唯一的，当存在多个合适的密文的时候，需要返回字典序最小的那个。

本题基本思路与【回溯】2023C-找到它一致，但需要着重考虑最小字典序的问题。

此时，搜索的方向数组 DIRECTIONS 里的顺序就非常重要。假设当前点为 (x, y)，那么其近邻点为：

• 上方：(x-1, y)
• 左方：(x, y-1)
• 右方：(x, y+1)
• 下方：(x+1, y)

显然，如果存在多个近邻点同时满足下一个字符的时候，按照上、左、右、下这个顺序来搜索的话，一定能够得到最小的字典序，因为坐标为更小字典序的近邻点被优先搜索了。

这也是极少数的，我们需要特别注意方向数组 DIRECTIONS 的顺序的题目。即：

思路展开 参考代码在「单词搜索」的回溯骨架上加了两处保证字典序最小的关键设计。第一处是起点的枚举顺序：主函数按行优先双重循环枚举 (i, j)，坐标小的起点先被尝试，所以第一个能匹配完整明文的起点必然是行列序号最小的。第二处是方向数组的顺序：DIRECTIONS 固定为上、左、右、下——对当前点 (x, y) 来说，四个近邻中 (x-1, y) 的坐标字典序最小、(x+1, y) 最大，按这个顺序深搜，每一步都优先延伸坐标更小的分支，于是搜索树里第一条被完整走通的路径就是字典序最小的密文。找到后立即在递归内部打印 path 并把 isFind 置真，之后所有尚未展开的递归调用在入口处直接返回，相当于一次全局剪枝。path 在状态更新时压入 (nx, ny)、回滚时弹出，起点坐标则作为初始路径在递归入口传入；全部起点试完仍未命中时输出 error。

复杂度分析

• 设密码本为 M × M 网格，明文长度为 N。起点候选最多 M² 个；每次回溯深度不超过 N，由于 check_list 至少挡住来路那一格，每层最多 3 个有效分支，单起点搜索上界为 O(3^N)，总时间复杂度上界为 O(M² × 3^N)。isFind 全局剪枝使找到答案后剩余搜索立即收束，实际代价通常远小于上界。
• 空间复杂度为 O(M² + N)：check_list 占 O(M²)，递归栈与 path 占 O(N)。