उन स्थानों का प्रतिशत ज्ञात करने का कार्यक्रम जहां नाइट चल सकता है और पायथन में बोर्ड नहीं छोड़ा है

मान लीजिए हमारे पास चार मान 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 में डालें
• एस में तत्वों का रिटर्न योग
• मुख्य विधि से निम्न कार्य करें -
• (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