this problem is minimal task Link can be solved by dp, i am using bfs or djikstra u can say , so i made a priority_queue and when first time when my string will be having the size of 2*n-1 means i had reached to end so this will be the answer lexicographically
see the code i am getting TLE no wrong answer i think worst complexity will be O(N^2) ,Please help
struct cmp {
bool operator()(const pair<pair<int,int>,string> &x, const pair<pair<int,int>,string> &y) const {
return x.second > y.second ;
}
};
int check(int i,int j,int n){
return i>=0 && j>=0 && i<n && j<n;
}
string ans;
vector<pair<int,int>>dir={{1,0},{0,1}};
string bfs(int i,int j,vector<vector<char>>&vec,vector<vector<int>>&vis,int n){
priority_queue<pair<pair<int,int>,string>,vector<pair<pair<int,int>,string>>,cmp>pq;
string s;
s+=vec[i][j];
pq.push({{i,j},s});
while(!pq.empty()){
auto it=pq.top();pq.pop();
string temp=it.second;
if(it.second.size()==(n*2 - 1)){
return it.second;
}
for(auto &i:dir){
int new_x=it.first.first+i.first;
int new_y=it.first.second+i.second;
if(check(new_x,new_y,n) && vis[new_x][new_y]==-1){
vis[new_x][new_y]=1;
pq.push({{new_x,new_y},temp+vec[new_x][new_y]});
}
}
}
}
void solve() {
// executing code from here
int t=1;
while (t--) {
int n;
cin >> n;
vector<vector<char>> vec(n,vector<char>(n,'.'));
vector<vector<int>> vis(n,vector<int>(n,-1));
for (int i = 0; i < n; i++){
for(int j=0;j<n;j++){
cin>>vec[i][j];
}
}
cout<<bfs(0,0,vec,vis,n)<<endl;
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// sieve();
solve();
return 0;
}



