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.