← 返回题目列表

Codeforces · 1031/D

D. 最小路径

中文机器翻译题面 查看原题

给定一个大小为 $$$n \times n$$$ 的矩阵,其中填充有小写英文字母。您最多可以更改此矩阵中的 $$$k$$$ 个字母。

考虑从左上角到右下角从一个单元向右或向下移动到其相邻单元的所有路径。每条路径都与由该路径访问的单元格中的所有字母组成的字符串相关联。因此,每个字符串的长度为 $$$2n - 1$$$。

在更改矩阵的最多 $$$k$$$ 单元格中的字母后,找到可与路径关联的字典顺序最小的字符串。

如果 $$$a$$$ 和 $$$b$$$ 中的第一个不同字母在 $$$a$$$ 中较小,则字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2000$$$, $$$0 \le k \le n^2$$$) — 矩阵的大小和可以更改的字母数量。

接下来的 $$$n$$$ 行包含一串 $$$n$$$ 小写英文字母,表示矩阵的一行。

输出

在更改矩阵中不超过 $$$k$$$ 个字母后,输出可与某些有效路径关联的字典顺序最小的字符串。

示例

输入 #1

4 2
abcd
bcde
bcad
bcde

输出 #1

aaabcde

输入 #2

5 3
bwwwz
hrhdh
sepsp
sqfaf
ajbvw

输出 #2

aaaepfafw

输入 #3

7 6
ypnxnnp
pnxonpm
nxanpou
xnnpmud
nhtdudu
npmuduh
pmutsnz

输出 #3

aaaaaaadudsnz

注意

在第一个示例测试用例中,可以将单元格 $$$(2, 1)$$$ 和 $$$(3, 1)$$$ 中的字母 'b' 更改为 'a',则最小路径包含单元格 $$$(1, 1), (2, 1), (3, 1), (4, 1), (4, 2), (4, 3), (4, 4)$$$。第一个坐标对应于行,第二个坐标对应于列。