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

更新于：2020年11月19日

837 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告