騎士が移動でき、Pythonでボードを離れることができない場所の割合を見つけるためのプログラム

4つの値n、x、y、およびkがあるとします。ここで、nはn x nのチェス盤を示し、x、y座標はナイトが（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）-
  • 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