About the Question in Edu Round Codeforces

Revision en2, by FreeHit, 2022-08-28 14:32:39

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English FreeHit 2022-08-28 14:34:21 947
en2 English FreeHit 2022-08-28 14:32:39 953
en1 English FreeHit 2022-08-28 14:19:23 273 Initial revision (published)