#include <bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define all(x) x.begin(), x.end()
#define sz(a) ((int) a.size())
#define pb push_back
#define fst first
#define snd second
using namespace std;
typedef long long ll;
const ll INF=1e18+5;
ll dp[30][30];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;cin>>n>>m;
vector<string>g(n);
L(i,0,n-1)cin>>g[i];
ll k;cin>>k;
dp[n-1][m-1] = 1;
R(i,n-1,0){
R(j,m-1,0){
if(i==n-1&&j==m-1)continue;
ll v=0;
if(i+1<n)v=min(INF,v+dp[i+1][j]);
if(j+1<m)v=min(INF,v+dp[i][j+1]);
dp[i][j]=v;
}
}
string ans(1,g[0][0]);
vector<pair<int,int>>path;
path.pb({0,0});
L(i,1,n+m-2){
bool vis[30][30];
L(i,0,29)memset(vis[i],0,sizeof(vis[i]));
vector<pair<int,int>>nxtPath;
for(auto &[x,y]:path){
if(x+1<n&&!vis[x+1][y]){
nxtPath.pb({x+1,y});
vis[x+1][y]=true;
}
if(y+1<m&&!vis[x][y+1]){
nxtPath.pb({x,y+1});
vis[x][y+1]=true;
}
}
for(char c='a';c<='z';c++){
ll ways=0;
for(auto &[x,y]:nxtPath)if(g[x][y]==c){
ways=min(INF,ways+dp[x][y]);
}
if(ways>=k){
ans+=c;
path.clear();
for(auto &[x,y]:nxtPath)if(g[x][y]==c){
path.pb({x,y});
}
break;
}else{
k-=ways;
}
}
}
cout<<ans<<endl;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
