如何确定一次可以拍摄（i，j）步骤的“骑士”是否可以覆盖NxN板？

Question

通常，骑士每次移动（1,2）步骤，即一个方向移动一步，另一个移动两步。在通用版本中，它可以一次移动（i，j）个步骤。

我不确定这是否是骑士的巡演问题，因为我不记得一次只能访问一个广场的限制。此外，答案只是一个“是/否”，我们不需要知道实际路径。

我想到的一个想法基本上是像图表一样对待棋盘上的点，然后先深入搜索所有有效的（i，j）棋步并将其标记为已访问。最后，如果有任何未访问的广场，那么这是不可能的。然而，这占用了N^2空间，我想知道是否有更简单的解决方案，因为这是一个是/否的问题。

Answer 1

它很简单。

如果NxN板和骑士移动a,b，则：

1. 如果满足gcd（A，B）== 1和
2. 如果中心可以到达**

奈特可以覆盖整个板子。

**为了确定中心可到达：

“让中心正方形是（X，Y）。然后，这些点对中的一个必须是在范围内（1..N，1。 .N）“

(x +/- a, y +/- b) and (x +/- b, y +/- a) 

其中基本上8点骑士可以移动，如果它在董事会的中心。