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