मान लीजिए हमारे पास चार मान 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) पर है। एक चाल में वह 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 लौटाएं - सभी चालों के लिए
dfs(x+dx, y+dy, k-1)/8का योग लौटाएं
- यदि
- मुख्य से:
round(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
