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.
It can be solved with BFS or DFS if you use coordinate compression first.
Okay, I'll look about coordinate compression. But if the grid is infinite, can co-compression still handle it? One more thing, if lets say that the maximum number of blocked squares is, say 200. Would you take a different approach then?
How would you implement infinite grid? If the constraints were smaller I would just use regular bfs/dfs to make it simple and save time since there is no need to use coordinate compression in that case.
I don't get it when you say how to implement infinite grid. The question is, given two points in an infinite maze with some blocked cells, is there a path between those two points? Here is what I think for infinite grid. If the blocked cells form a closed interval containing either only target or only source, then it is impossible to reach otherwise we can always reach. Now, how to check if some closed interval is formed around the target or source? I read about it and it is confusing, I did not understand it and so cannot explain it. If you have any ideas, let me know. The same idea can be applied for the finite grid with minor changes. Thanks for the question!
Also, why are you talking about infinite grids when the description says 1 million maximum?
Is 1 million equal to infinity to you? If you ever win a million dollar and start buying a lot of houses and dozens of Lamborghini cars because your money is infinite, you will have some financial problems.
No, sir. That infinite grids is a follow-up question if you come up with a solution to the finite one.
Ahhh, I see. Then you'll handle it the exact same way.
Well if the grid is infinite I will assume that you are given two coordinates describing your possition, two coordinates describing the target and a map with key of let's say x coordinate and vector of y coordinates such that all cells (x, y) are blocked(I don't see any other ways of storing such information for infinite grid). You can start a recursion over any blocked cell and move to all connected blocked cells (since you can move in 4 directions blocked cells are connected in 8 directions because diagonal will still block you). You remember which cells you visited and which not. If during recursion any part of it ends without going back to already visited cell it means that those blocked cells don't form enclosed interval so you can ignore them. Otherwise if you come back to already visited cell than that interval is enclosed and you can do floodfill algorithm to see are target and start position in that interval. If one of them is and other is not you can end program saying there is no path. Otherwise you need to continue recursion. You would also need to compress coordinates for floodfill to work efficiently. Total complexity would be the number of blocked cells + all floodfills.
I have found a simpler approach online. No compression, no flood-fill. Only two BFS.
"The target is reachable if the source is not blocked, and the target is not blocked. With 200 blocks, we only need to travel some limited distance to check that we are not blocked. When we run BFS, our queue contains the front "wave" of our search. If the number of cells is greater than the number of blocks, this wave cannot be contained. So, we do BFS from source and target. If both are uncontained, we return true else we return false."
This approach makes sense to me. What are your thoughts on this?
This is a great solution. I have also noticed that given n blocked cells if your starting position(let's say 0, 0 for simplicity) is enclosed it is not possible to get to point x, y such that sum of absolute values of x and y is greater than n/2 — 2 (you can check this with simple geometry). It is now easier to just check with dfs if you can get to any of those positions. It is essentially not much different from your solution, but because dfs goes depth first I think it will be faster
If the grid is infinite, there will still be an origin and a destiny with specific coordinates, so you'll consider those for compression.
And 200 is nothing. Coordinate compression will work well even with $$$10^8$$$ coordinates total (that's $$$10^4$$$ vertical and $$$10^4$$$ horizontal points).
Good that compression will work even if grid is infinite. Regarding the number of blocked cells, I didn't mean to say that 200 blocks are too much, how to handle it. In fact, I said that 200 blocks are much less, so, maybe we have an simpler solution to it. For example, look at my above reply to psruk . Regards.
It doesn't get much simpler than coordinate compression + DFS. Trying to find out if the blocked cells divide the grid in 2 components is much much harder.
Okay. Let's wait and see if someone comes with a simpler solution. I'll tag you there.
Here is the simpler solution. "The target is reachable if the source is not blocked, and the target is not blocked. With 200 blocks, we only need to travel some limited distance to check that we are not blocked. When we run BFS, our queue contains the front "wave" of our search. If the number of cells is greater than the number of blocks, this wave cannot be contained. So, we do BFS from source and target. If both are uncontained, we return true else we return false."
This approach makes sense to me. What are your thoughts on this?
I don't know what "wave" means, and that soution doesn't specify how to check if we are blocked or not.
Still, the simplest solution is to compress coordinates and just do a BFS/DFS.
Wave is the outermost layer of our search in BFS. How to check if we are blocked? Simple. If the queue becomes empty, we are blocked.
Then you're still doing BFS, and how do you plan to make it fit in time without coordinate compression if both coordinates can be up to $$$10^6$$$?
You need coordinate compression, like I said in my first post.
This question is similar to this one383 B