Recently in an interview, I was asked this question:
You are given two cells on a chess board, one is starting cell and another one is destination cell. You will get a list of cells also, which represents blocked cells, that means you can't drop on this cells during a tour. Now you have to find a minimum number of steps to reach destination cell from the starting cell with a Knight. Given that the chess grid is infinite.
So my thought was using Breadth First Search, but the problem is if the destination is not reachable, the code will be in an infinite loop.
How to solve it?
Given that there are only finitely many blocking cells, if the two cells are not reachable from each other, one of the cells must have only finitely many reachable cells.
(otherwise, if there are two infinite region, the "barrier" between the region must take infinitely many blocking cells)
Now the solution is quite obvious. Just do a parallel BFS from both the source and the target. If either search terminates, then there are no path.