At first seeing question i just got into using bfs on matrix to get minimum distance if possible but cant get to solution with it. can it be done with bfs?? here is link for question- https://mirror.codeforces.com/contest/1721/problem/B
Here is my pseudo code:
ll n,m,sx,sy,d; ll dist[1010][1010]={0}; bool check(ll x,ll y){ if(x<0||x>=n||y<0||y>=m||dist[x][y]!=0||abs(sx-1-x)+abs(sy-y-1)<=d)return false; return true; }
void solve(){
cin>>n>>m>>sx>>sy>>d; queueq; q.push({0,0}); dist[0][0]=1; while(!q.empty()){ ll size=q.size(); while(size--){ ll tx=q.front().ff; ll ty=q.front().ss; q.pop(); if(check(tx,ty+1)){ dist[tx][ty+1]=dist[tx][ty]+1; q.push({tx,ty+1}); } if(check(tx+1,ty)){ dist[tx+1][ty]=dist[tx][ty]+1; q.push({tx+1,ty}); } if(check(tx,ty-1)){ dist[tx][ty-1]=dist[tx][ty]+1; q.push({tx,ty-1}); } if(check(tx-1,ty)){ dist[tx-1][ty]=dist[tx][ty]+1; q.push({tx-1,ty}); } } }
if(dist[n-1][m-1]==0){cout<<-1<<endl;return;} cout<<dist[n-1][m-1]-1<<endl;
return; }