algorithm - 带阻塞单元的无限网格骑士之旅

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.

所以我的想法是使用广度优先搜索，但问题是如果目的地不可达，代码将陷入无限循环。

如何解决？

Answer 1

鉴于只有有限多个阻塞单元格，如果两个单元格彼此不可达，则其中一个单元格必须只有有限多个可达单元格。

(否则，如果有两个无限区域，区域之间的“屏障”必须采取无限多个阻挡单元格)

现在解决方案很明显了。只需从源和目标进行并行 BFS。如果任一搜索终止，则没有路径。