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

Arnab Chakraborty

更新於：2020年11月19日

837 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習