传送门
唉考试的时候写错了两个细节调了一个多小时根本没调出来。
下来又调了半个小时才过。
其实很简单。
我们先dpdpdp出最开始最多多少个连续的aaa.
然后对于没法继续连续下去的用贪心+bfsbfsbfs来弄就行了。
技不如人，告辞。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,k,mx[2005][2005],maxA;
char mp[2005][2005];
bool vis[2005][2005];
queue<pair<int,int> >q,s;
inline void dfs(int x,int y,int dep){
if(~mx[x][y])return;
if(x==1&&y==1)mx[x][y]=(mp[x][y]=='a');
else{
if(x^1)dfs(x-1,y,dep-1);
if(y^1)dfs(x,y-1,dep-1);
mx[x][y]=(mp[x][y]=='a')+max(mx[x-1][y],mx[x][y-1]);
}
if(dep<maxA)return;
if(mx[x][y]>=dep-k){
if(dep==maxA)q.push(make_pair(x,y));
else if(dep>maxA){
while(!q.empty())q.pop();
q.push(make_pair(x,y)),maxA=dep;
}
}
}
int main(){
memset(mx,-1,sizeof(mx)),scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)scanf("%s",mp[i]+1);
maxA=k;
dfs(n,n,n*2-1);
int sig=26;
string tmp;
for(int i=1;i<=min(maxA,n*2-1);++i)tmp=tmp+'a';
if(maxA>=n*2-1)return cout<<tmp,0;
if(!maxA)q.push(make_pair(1,1)),tmp=tmp+mp[1][1];
for(int i=maxA?maxA+1:2;i<=n*2-1;++i){
sig=26;
while(!q.empty()){
pair<int,int>t=q.front();
q.pop();
int x=t.first,y=t.second,i,j;
i=x+1,j=y;
if(i<=n&&!vis[i][j]){
vis[i][j]=1;
if(mp[i][j]-'a'==sig)s.push(make_pair(i,j));
else if(mp[i][j]-'a'<sig){
while(!s.empty())s.pop();
s.push(make_pair(i,j)),sig=mp[i][j]-'a';
}
}
i=x,j=y+1;
if(j<=n&&!vis[i][j]){
vis[i][j]=1;
if(mp[i][j]-'a'==sig)s.push(make_pair(i,j));
else if(mp[i][j]-'a'<sig){
while(!s.empty())s.pop();
s.push(make_pair(i,j)),sig=mp[i][j]-'a';
}
}
}
tmp=tmp+(char)(sig+'a');
while(!s.empty())q.push(s.front()),s.pop();
}
cout<<tmp;
return 0;
}