首先可以发现操作肯定用在前面，当然如果本身就为 a 就不用施法了,因为前缀字典序越小,整体字典序也越小。

所以定义 $g_{i,j}$ 从第 $1$ 行第 $1$ 列走到第 $i$ 行第 $j$ 列最少经过多少个非 a 字母。

下面设原矩阵的第 $i$ 行第 $j$ 列 为 $s_{i,j}$。

转移：

$$g_{i,j}=\min(g_{i,j-1},g_{i+1,j})+[s_{i,j}\not=\texttt{a}]$$

然后可以发现如果 $g_{i,j} \le k$，不妨把 所有 $s_{i,j}$ 设为 a。

这样一来就消除 $k$ 的影响了。

接下来只需要要求字典序最小的路径。 用 bfs 贪心一步步的走,每次只保留当前能走最小字符的那些路径.