โปรแกรมค้นหาขั้นตอนขั้นต่ำในการไปถึงตำแหน่งเป้าหมายโดยอัศวินหมากรุกใน Python

สมมติว่าเรามีสองค่า r และ c หากอัศวินหมากรุกถูกวางไว้ที่พิกัด (0, 0) ที่จุดเริ่มต้นในกระดานหมากรุกขนาดใหญ่ที่ไม่มีขีด จำกัด เราต้องหาจำนวนการเคลื่อนไหวขั้นต่ำที่จะไปถึงที่ตั้ง (r, c) อัศวินจะเล่นตามสไตล์การเล่นหมากรุก โดยจะเลื่อนสี่เหลี่ยมออกไปสองช่องในแนวนอนและหนึ่งช่องในแนวตั้ง หรือสองช่องในแนวตั้งและอีกหนึ่งช่องในแนวนอน

ดังนั้น หากอินพุตเป็น r =6, c =1 เอาต์พุตจะเป็น 3 สีแดงคือตำแหน่งเริ่มต้น สีเขียวคือขั้นสุดท้าย และสีเหลืองคือขั้นกลาง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถ้า r
• สลับ r และ c

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution:
   def solve(self, r, c):
      if r < c:
         r, c = c, r
      if (r, c) == (1, 0):
         return 3
      if (r, c) == (2, 2):
         return 4
      delta = r - c
      if c > delta:
         return delta - 2 * ((delta - c) // 3)
      else:
         return delta - 2 * ((delta - c) // 4)
ob = Solution()
r = 6
c = 1
print(ob.solve(r, c))

อินพุต

6, 1

ผลลัพธ์

3