Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

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://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 FreeHit 2022-08-28 14:34:21 947
en2 FreeHit 2022-08-28 14:32:39 953
en1 FreeHit 2022-08-28 14:19:23 273 Initial revision (published)