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;
}








Dude, did you really write that code?
1) Sorry, but the TC is O(n3logn), with the constraint of n <= 3000, n3logn is very large, so gives TLE
2) Avoid storing strings in the priority queue, this makes your BFS slower as strings are heavy to copy
Hope this helps..
Dude, your time complexity is wrong! In the worst case, there will be $$$O(n^2)$$$ values in your priority_queue, and each value stores a string with $$$O(n)$$$ length. The comparison of two strings in priority_queue costs $$$O(n)$$$. Hence, Your time complexity is $$$O(n^3 \log n)$$$.
Here's my code: