Python程式：計算騎士在棋盤上移動且不離開棋盤的機率

假設我們有四個值n、x、y和k。其中n表示n x n的棋盤，座標(x, y)表示騎士的初始位置。騎士必須走k步，每一步都可以隨機選擇8個方向中的任何一個方向移動。我們需要找到騎士在走完k步後仍然留在棋盤上的機率百分比（四捨五入到最接近的整數）。條件是：一旦騎士離開棋盤，就不能再回到棋盤上。

例如，如果輸入為n = 8，(x = 0, y = 0)，k = 1，則輸出為50。因為這是一個8x8的棋盤，騎士的初始位置為(1, 1)。它可以走k = 1步。走一步後，它只有在8個位置中的4個位置上才會留在棋盤內，而在其他位置上則會落在棋盤外。所以機率是50%。

為了解決這個問題，我們將遵循以下步驟：

• 建立一個移動列表：[(1, 2) ,(1, -2) ,(-1, 2) ,(-1, -2) ,(2, 1) ,(2, -1) ,(-2, 1) ,(-2, -1) ]
• 定義一個函式dfs()。它將接收x、y、k作為引數。
• 如果(x, y)不在棋盤範圍內，則
  • 返回0
• 如果k等於0，則
  • 返回1
• s = 空列表
• 對所有移動(dx, dy) in moves：
  • x = dfs(x + dx, y + dy, k - 1) / 8
  • 將x新增到s中
• 返回s中所有元素的和
• 在主方法中執行以下操作：
• 返回(dfs(x, y, k) * 100)四捨五入到最接近的整數的結果

讓我們來看下面的實現，以便更好地理解：

示例

線上演示

moves = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
class Solution:
   def solve(self, n, x, y, k):
      def dfs(x, y, k):
         if x < 0 or y < 0 or x >= n or y >= n:
            return 0
         if k == 0:
            return 1
         return sum(dfs(x + dx, y + dy, k - 1) / 8 for dx, dy in moves)
      return int(dfs(x, y, k) * 100)
ob = Solution()
n = 8
x = 1
y = 1
k = 1
print(ob.solve(n, x, y, k))

輸入

8, 1, 1, 1

輸出

0

Arnab Chakraborty

更新於：2020年11月19日

瀏覽量：126

開啟您的職業生涯

完成課程獲得認證

開始學習