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

# | User | Rating |
---|---|---|

1 | tourist | 3751 |

2 | Benq | 3727 |

3 | cnnfls_csy | 3691 |

4 | Radewoosh | 3651 |

5 | jiangly | 3632 |

6 | orzdevinwang | 3559 |

7 | -0.5 | 3545 |

8 | inaFSTream | 3478 |

9 | fantasy | 3468 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 178 |

2 | awoo | 167 |

3 | BledDest | 165 |

4 | Um_nik | 164 |

5 | maroonrk | 163 |

6 | SecondThread | 160 |

7 | nor | 158 |

8 | -is-this-fft- | 154 |

9 | kostka | 146 |

10 | Geothermal | 144 |

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

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/27/2023 02:10:57 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

even though over all worst time will be O(1e7) this will run. can you explain if will go through graph.

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.

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

Note: spoiler parts contains hints to the solution

The 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