带阻塞单元的无限网格骑士之旅
Knight tour on Infinite Grid with blocking cell
最近在面试中，有人问我这个问题：
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.
所以我的想法是使用广度优先搜索，但问题是如果目的地不可达，代码将陷入无限循环。
如何解决？
鉴于只有有限多个阻塞单元格，如果两个单元格彼此不可达，则其中一个单元格必须只有有限多个可达单元格。
（否则，如果有两个无限区域，区域之间的"barrier"必须有无限多个块单元格）
现在解决方案很明显了。只需从源和目标进行并行 BFS。如果任一搜索终止，则没有路径。
您可以将棋盘的大小限制为比起始单元格和目标单元格的最大坐标大 3 行 3 列，即：
rows = Max(starting cell row no + 3, destination cell row no + 3)
cols = Max(starting cell column no + 3, destination cell column no + 3)
为什么？如果您考虑骑士的移动方式，您会发现在棋盘的上述限制内，您总是可以以最少的移动次数到达任何目标单元格。最 "costly" 的情况是单元格对角对齐，例如起始单元格 A1 和目标单元格 B2，然后您需要移动 C2、E3、C4，最后移动 B2 - 4。所有其他情况都更快并且需要更少 "space".
最近在面试中，有人问我这个问题：
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.
所以我的想法是使用广度优先搜索，但问题是如果目的地不可达，代码将陷入无限循环。
如何解决？
鉴于只有有限多个阻塞单元格，如果两个单元格彼此不可达，则其中一个单元格必须只有有限多个可达单元格。
（否则，如果有两个无限区域，区域之间的"barrier"必须有无限多个块单元格）
现在解决方案很明显了。只需从源和目标进行并行 BFS。如果任一搜索终止，则没有路径。
您可以将棋盘的大小限制为比起始单元格和目标单元格的最大坐标大 3 行 3 列，即：
rows = Max(starting cell row no + 3, destination cell row no + 3)
cols = Max(starting cell column no + 3, destination cell column no + 3)
为什么？如果您考虑骑士的移动方式，您会发现在棋盘的上述限制内，您总是可以以最少的移动次数到达任何目标单元格。最 "costly" 的情况是单元格对角对齐，例如起始单元格 A1 和目标单元格 B2，然后您需要移动 C2、E3、C4，最后移动 B2 - 4。所有其他情况都更快并且需要更少 "space".