Codeforces Round #517 (Div. 2, based on Technocup 2019 Elimination Round 2)：D. Minimum path（思维）

D. Minimum path
time limit per test1.5 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given a matrix of size n×n filled with lowercase English letters. You can change no more than k letters in this matrix.

Consider all paths from the upper left corner to the lower right corner that move from a cell to its neighboring cell to the right or down. Each path is associated with the string that is formed by all the letters in the cells the path visits. Thus, the length of each string is 2n−1.

Find the lexicographically smallest string that can be associated with a path after changing letters in at most k cells of the matrix.

A string a is lexicographically smaller than a string b, if the first different letter in a and b is smaller in a.

Input
The first line contains two integers n and k $(1≤n≤2000, 0≤k≤n^2)$(1≤n≤2000,0≤k≤n2) — the size of the matrix and the number of letters you can change.

Each of the next n lines contains a string of n lowercase English letters denoting one row of the matrix.

Output
Output the lexicographically smallest string that can be associated with some valid path after changing no more than k letters in the matrix.

Examples
input
4 2
abcd
bcde
bcad
bcde
output
aaabcde
input
5 3
bwwwz
hrhdh
sepsp
sqfaf
ajbvw
output
aaaepfafw
input
7 6
ypnxnnp
pnxonpm
nxanpou
xnnpmud
nhtdudu
npmuduh
pmutsnz
output
aaaaaaadudsnz

思路：因为有k次修改机会，且要求字典序最小，那么当然是尽量把前面的字符变为’a’，那么我们可以求出序列中前缀全为’a’的最长长度。

然后我们从这些前缀的最后一个字符开始找出一条到达$(n,n)$(n,n)的字典序最小的路径，我们把这些点走一步可能得到的字符找出来，并找到最小的那个字符加入到答案，然后再以这些最小的字符为起点，重复上述操作。

#include<bits/stdc++.h>
using namespace std;
const int MAX=2e3+10;
char s[MAX][MAX];
int v[MAX][MAX];
int d[MAX][MAX];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
    memset(d,0,sizeof d);
    int ma=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i>1&&j>1)d[i][j]=min(d[i-1][j],d[i][j-1]);
            else if(i>1)d[i][j]=d[i-1][j];
            else if(j>1)d[i][j]=d[i][j-1];
            d[i][j]+=(s[i][j]!='a');
            if(d[i][j]<=m)ma=max(ma,i+j-1);//找出'a'的最长长度
        }
    }
    queue<int>p,q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(d[i][j]<=m&&i+j-1==ma)//用这些点扩展求出答案
            {
                p.push(i);
                p.push(j);
            }
        }
    }
    string ans="";
    for(int i=1;i<=ma;i++)ans+='a';
    if(ma==0)
    {
        p.push(1);
        p.push(1);
        ans+=s[1][1];
        ma++;
    }
    for(int i=ma+1;i<=2*n-1;i++)
    {
        q=p;
        char nex='z';
        while(!p.empty())
        {
            int x=p.front();p.pop();
            int y=p.front();p.pop();
            if(x+1<=n)nex=min(nex,s[x+1][y]);//求出下一步得到的最小字符
            if(y+1<=n)nex=min(nex,s[x][y+1]);
        }
        ans+=nex;
        while(!q.empty())
        {
            int x=q.front();q.pop();
            int y=q.front();q.pop();
            if(x+1<=n&&s[x+1][y]==nex&&v[x+1][y]==0)//以最小字符为起点继续扩展
            {
                p.push(x+1);
                p.push(y);
                v[x+1][y]=1;
            }
            if(y+1<=n&&s[x][y+1]==nex&&v[x][y+1]==0)
            {
                p.push(x);
                p.push(y+1);
                v[x][y+1]=1;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}