使用Python查找国际象棋马的最小步数到目标位置的程序

使用Python查找国际象棋马的最小步数到目标位置的程序

假设我们有两个值r和c。如果国际象棋马开始在一个无限大的棋盘上的坐标(0, 0)上,我们必须找到到达位置(r, c)的最小移动步数。马将遵循国际象棋的相同走法。它向水平方向移动两个方格和垂直方向移动一个方格,或向垂直方向移动两个方格和水平方向移动一个方格。

所以,如果输入是r = 6,c = 1,那么输出将是3,红色是初始位置,绿色是最终步骤,黄色是中间步骤。

使用Python查找国际象棋马的最小步数到目标位置的程序

要解决这个问题,我们将按照以下步骤进行−

  • 如果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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程