Need help in a maze problem.

Revision en2, by Pie-Lie-Die, 2020-05-20 16:05:21

In a 1 million by 1 million grid, the coordinates of each grid square are (x, y) with 0 <= x, y < 10^6.

We start at the source square and want to reach the target square. Each move, we can walk to a 4-directionally adjacent square in the grid that isn't in the given list of blocked squares.

Return true if and only if it is possible to reach the target square through a sequence of moves.

The signature of the function is as follows:-

bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target)

Standard BFS and bi-directional BFS are both resulting in MLE (Stack Overflow). What other approaches can we take for this problem?

Also, another follow-up question being, what if the grid is infinite?

Kindly mention your thoughts along with explanation.

Thanks.

Tags #help, #codeforces, maze, #bfs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Pie-Lie-Die 2020-05-20 16:05:21 4
en1 English Pie-Lie-Die 2020-05-20 16:04:24 861 Initial revision (published)