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

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

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