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

Question

通常，骑士一次移动 (1,2) 步，即向一个方向移动 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 个点。