### FreeHit's blog

By FreeHit, history, 13 months ago,

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

• +1

| Write comment?
 » 13 months ago, # | ← Rev. 2 →   +1 It doesn't say: "The sum of n*m over all test cases does not exceed 10^3". So O(t*n*m) exceed time limit.
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 even though over all worst time will be O(1e7) this will run. can you explain if will go through graph.
•  » » » 13 months ago, # ^ |   0 For BFS the worst case would be searching the entire graph, which can happen if the laser has a distance of 0 and there exists a path every time. n and m have max values of 1000, so the size of the grid can be up to 10^6. With 10^4 possible test cases this could mean around 10^10 tiles searched in worst case, which will exceed time limit.
•  » » » » 13 months ago, # ^ |   0 if some how constraints permits bfs what will be the code:i coded it but gives wrong outputs even matched all conditions: 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; }
•  » » » » » 13 months ago, # ^ | ← Rev. 2 →   0 Note: spoiler parts contains hints to the solutionThe constraints make BFS impossible to use because it's not possible to check up to 10^10 tiles in 2 seconds. Hint for problemBFS isn't even needed for this question because if there exists a path, the minimum distance would be the same as if there was no laser in the grid. Looking at your last submission you correctly found that a path does not exist if the laser is touching the top and bottom walls or the left and right walls, but there are other scenarios where a path does not exist