使用Python查找国际象棋马的最小步数到目标位置的程序
假设我们有两个值r和c。如果国际象棋马开始在一个无限大的棋盘上的坐标(0, 0)上,我们必须找到到达位置(r, c)的最小移动步数。马将遵循国际象棋的相同走法。它向水平方向移动两个方格和垂直方向移动一个方格,或向垂直方向移动两个方格和水平方向移动一个方格。
所以,如果输入是r = 6,c = 1,那么输出将是3,红色是初始位置,绿色是最终步骤,黄色是中间步骤。
要解决这个问题,我们将按照以下步骤进行−
- 如果r < c,则
- 交换r和c
- 如果(r,c)与(1, 0)相同,则
- 返回3
- 如果(r,c)与(2, 2)相同,则
- 返回4
- 设delta := r – c
- 如果c > delta,则
- 返回delta – 2 *( (delta – c) / 3的商)
- 否则,
- 返回delta – 2 *( (delta – c) /4的商)
让我们看一下以下实现以获取更好的理解−
示例
class Solution:
def solve(self, r, c):
if r < c:
r, c = c, r
if (r, c) == (1, 0):
return 3
if (r, c) == (2, 2):
return 4
delta = r - c
if c > delta:
return delta - 2 * ((delta - c) // 3)
else:
return delta - 2 * ((delta - c) // 4)
ob = Solution()
r = 6
c = 1
print(ob.solve(r, c))
输入
6, 1
输出
3