สมมติว่าเรามีสี่ค่า 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 ก้าว ก้าวหนึ่งก้าว มันจะอยู่ในกระดานเพียง 4 จาก 8 ตำแหน่ง และจะนอนข้างนอกที่ตำแหน่งอื่น 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
