//Just try and the idea will come
#include<bits/stdc++.h>
#define int long long int
using namespace std;
set<pair<string,pair<int,int>>>st;
int n,m,i,j,x,y,dp[31][31],k;
string val,dis[31][31][31][31],res="";
pair<int,int>path[31][31][31][31],nxt[31][31][31][31];
char a[31][31];
main(){
cin>>n>>m;
dp[1][1]=1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
cin>>a[i][j];
dp[i][j]+=dp[i-1][j]+dp[i][j-1];
for(int ii=1;ii<=n;ii++)
for(int jj=1;jj<=m;jj++)dis[i][j][ii][jj]="zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz";
}
cin>>k;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
dis[i][j][i][j]="";
dis[i][j][i][j]+=a[i][j];
st.insert({dis[i][j][i][j],{i,j}});
while(!st.empty()){
auto v=*st.begin();
x=v.second.first;
y=v.second.second;
val=v.first;
st.erase(st.begin());
if(x+1<=n&&val+a[x+1][y]<dis[i][j][x+1][y]){
st.erase({dis[i][j][x+1][y],{x+1,y}});
dis[i][j][x+1][y]=val+a[x+1][y];
path[i][j][x+1][y]={x,y};
st.insert({dis[i][j][x+1][y],{x+1,y}});
}
if(y+1<=m&&val+a[x][y+1]<dis[i][j][x][y+1]){
st.erase({dis[i][j][x][y+1],{x,y+1}});
dis[i][j][x][y+1]=val+a[x][y+1];
path[i][j][x][y+1]={x,y};
st.insert({dis[i][j][x][y+1],{x,y+1}});
}
}
x=n,y=m;
while(x&&y){
pair<int,int>tmp={x,y};
int xx=x;
x=path[i][j][x][y].first;
y=path[i][j][xx][y].second;
nxt[i][j][x][y]=tmp;
}}
x=y=1;
while(!(x==n&&y==m)){
i=nxt[x][y][x][y].first;
j=nxt[x][y][x][y].second;
res+=a[x][y];
if(k>dp[n-i+1][m-j+1]){
k-=dp[n-i+1][m-j+1];
if(i==x+1)y++;
else x++;
}else{
x=i,y=j;
}
}
res+=a[n][m];
cout<<res;
}
Compilation message
kthpath.cpp:10:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
29304 KB |
Output is correct |
| 2 |
Correct |
29 ms |
29564 KB |
Output is correct |
| 3 |
Correct |
30 ms |
30300 KB |
Output is correct |
| 4 |
Incorrect |
38 ms |
34808 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
