Can anyone please tell how to approach the following problem

Please look into the problem and tell me how to solve it.


I have tried BFS approach, but it is giving TLE.

Can you send your code

1 Like

You can optimize time complexity by reducing the range

From this earlier post click here

1 Like

check out the post…

#include <bits/stdc++.h>
#define MAX 10000000
#define ull unsigned long long
using namespace std;

int X[] = {0,1,0,-1};
int Y[] = {-1,0,1,0};
int arr[301][301];

bool valid(int x, int y, int n, int m) {
return x>=0 && x<n && y>=0 && y<m;
}

int getMinEffort(int n,int m) {
queue<pair<int,int>> q;
q.push(make_pair(0,0));
bool visited[n][m];
memset(visited,false,sizeof(visited));
visited[0][0] = true;
queue efforts;
pair<int,int> point;
efforts.push(0);
while(!q.empty()) {
point = q.front();
q.pop();
int prev = efforts.front();
int x = point.first, y = point.second;
visited[x][y] = true;
if(x!=n-1 || y!=m-1)
efforts.pop();
for(int i = 0;i < 4;i++) {
int u = x+X[i], v = y+Y[i];
if(valid(u,v,n,m) && !visited[u][v]) {
q.push(make_pair(u,v));
int cur = abs(arr[x][y]-arr[u][v]);
efforts.push(max(cur,prev));
}
}
}
int ans = MAX;
while(!efforts.empty()) {
ans = min(ans,efforts.front()),efforts.pop();
}
// cout<<ans<<endl;
return ans;
}

int main() {
// ios_base::sync_with_stdio(false);cin.tie(0).cout.tie(0);
int n,m;
scanf("%d%d",&n,&m);
// cin>>n>>m;
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)
scanf("%d",&arr[i][j]);
int answer = getMinEffort(n,m);
cout<<answer<<"\n";
return 0;
}

sorry, can’t help in C++ but try out the above mentioned technique once.
See the post i shared. @supreetsingh10 also had a similar doubt in his code(C++14) and it worked out fine

1 Like

Which range u are talking about?

like loops you know, while/for/ etc…
For has a range function in PYTH and it has helped me avoid TLE before

1 Like