好久没有发过题解了。最近的练习转向了算法难度较低的一些题目，因为发现在 CF&AT 中很多没有涉及什么进阶算法的题目我都做不出。。。模板不是算法竞赛的魅力所在，思维才是。

给定一个字符矩阵，可以修改 $k$ 次，求左上到右下走所经过的字典序最小的字符串。

首先有个非常简单的想法，前面的 $k$ 个肯定都是要改成 a 的。
因为输入串中可能也有一些 a, 所以首先想到要找到一些位置使得从 $(1, 1)$ 到这里的路径能够全部被改成 $a$, 可以很容易地用 dp 解决，$f_{i, j}$ 表示从 $(1, 1)$ 到 $(i, j)$ 路径上最多的 a 的个数，若 $f_{i, j} + k \ge i+j-1$ 那么就是可以的，若 $f_{n,n} + k \ge 2n-1$ 那么就可以直接退出了。

因为我们要恰好用 $k$ 个，所以考虑是否一定存在这样的位置使得 $f_{i, j} + k = i+j-1$ （$k$ 不为 $0$ 的时候）。
想想如果不存在这样的一个点会怎样，因为 $i+j-1$ 的变化是连续的，而 $f$ 的变化可能有跳跃，所以这种情况一定就是 $i+j-1$ 只移动了 $1$ 而 $f$ 增加（或减少）了很多， 那么就继续移动这个点，如果 $f$ 要维持他的优势不被 $i+j-1$ 赶上，就得在赶上之前继续增加，而如果这样能一直增加下去，那么 $f_{n, n} + k$ 就大于 $2n-1$ 了，与前提矛盾。
$f$ 减小时情况同理。所以一定有至少一个这样的位置。

将这些位置找出来，然后的目标就是要找出后面的字典序最小是什么。
如果向下和向右不重复，那么直接走就行了，所以考虑若向下的和向右的是一样的情况。可以用 $d_i$ 存下走到距离起点长度为 $i$ 的点集合，然后向两个方向拓展，并把所有扩展到能拓展的最小字符的点全部放进 $d_{i+1}$ 里，并且记下是从哪里来的，然后继续找。其实就是一个记下了每一步状态的 bfs。
因为每个点只需要入队一次，而只需要跑最多 $2n$ 次，所以这个搜索是 $n^2$ 级别的、

实现上需要注意判断 $k = 0$ 的情况，还有一些细节就看代码吧。
自己写的时候感觉实现有一点丑陋，写完之后对比了一下现有题解，发现我写得还是挺短的。

代码。

#include <cstdio>
#include <vector>
#include <algorithm>
const int N = 2005;
int n, k, f[N][N];
bool vis[N][N];
int dx[3] = {0, 1, 0},	
	dy[3] = {0, 0, 1};
struct twt { int x, y, pre; };
std::vector<twt> d[N+N];
char ans[N+N], s[N][N];
int main() {
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i++) scanf("%s", s[i]+1);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			f[i][j] = std::max(f[i-1][j], f[i][j-1]) + (s[i][j] == 'a');
	if(k >= n+n-1 || f[n][n] + k > n+n-1) {
		for(int i = 1; i <= n+n-1; i++) ans[i] = 'a';
		printf("%s", ans+1);
		return 0;
	}
	int max = 0;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(f[i][j] + k == i+j-1 && i+j-1 > max) max = i+j-1;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(f[i][j] + k == i+j-1 && i+j-1 == max) 
				d[i+j-1].push_back((twt){i, j, -1}), vis[i][j] = 1;
	if(max == 0) d[1].push_back((twt){1, 1, -1});
	for(int t = (max?max:1); t <= n+n-2; t++) {
		char min = 'z';
		for(int j = 0; j < (signed)d[t].size(); j++) 
			for(int k = 1; k <= 2; k++) {
				int xx = d[t][j].x+dx[k], yy = d[t][j].y+dy[k];
				if(xx <= n && yy <= n && !vis[xx][yy]) min = std::min(s[xx][yy], min);
			} 
		for(int j = 0; j < (signed)d[t].size(); j++) 
			for(int k = 1; k <= 2; k++) {
				int xx = d[t][j].x+dx[k], yy = d[t][j].y+dy[k];
				if(xx <= n && yy <= n && !vis[xx][yy] && s[xx][yy] == min) 
					d[t+1].push_back((twt){xx, yy, j}), vis[xx][yy] = 1;
			} 
	}
	for(int i = 1; i <= max; i++) ans[i] = 'a';
	for(int i = n+n-1, x = n, y = n, pre = d[n+n-1][0].pre; i > max; i--) {
		ans[i] = s[x][y];
		if(i != max+1)x = d[i-1][pre].x, y = d[i-1][pre].y, pre = d[i-1][pre].pre;
	}
	 printf("%s", ans+1);
	return 0;
}