T4 寻宝（treasure）

首先考虑没有法术的情况，那么很显然，直接从左上角起点开始往右和下找，每次都取当前次字典序更小的那个字母，如果有多个相同的，就全部考虑进去，在下一步中将所有的这些点当作起点一起考虑。其实就是类似使用 BFS 处理的分层最短路。

当我们使用里法术之后呢？很显然，为了使最终的答案字典序最小，肯定将从起点开始，将经过的所有非字母 $a$ 的字母全部变为字母 $a$，这样得到的字典序最小。那么，我们将使用 $k$ 次法术最远能够到的地方全部计算出来，再用 BFS 的方法后半部分内容，也能找到对应的答案，具体如下。

如何统计使用 $k$ 次法术能到达的最远地方？我们可以使用 dp。定义 $f_{i,j}$ 表示从起点开始，到坐标 $(i,j)$ 的路径上，最少非 $a$ 字母数量。转移为

那么，只要 $f_{i,j} \le k$，我们就能使从起点开始到 $(i,j)$ 的路径上最后所有的小写字母均为 $a$。而我们要字典序最小，就需要找出符合要求的答案里边的值 $i+j$ 最大的那一些（即路径最长，前缀 $a$ 最多）。再从这些满足最大值的点开始进行 BFS 分层处理，就能找出最终字典序最小的序列。