Chương trình tìm các bước tối thiểu để đạt được vị trí mục tiêu của một hiệp sĩ cờ vua bằng Python

Giả sử chúng ta có hai giá trị r và c. Nếu một quân cờ được đặt ở tọa độ (0, 0) lúc đầu trong một bàn cờ lớn vô hạn, chúng ta phải tìm số nước đi tối thiểu để đến được vị trí (r, c). Hiệp sĩ sẽ đi theo phong cách di chuyển tương tự như cờ vua. Nó di chuyển hai hình vuông ra xa theo chiều ngang và một hình vuông theo chiều dọc, hoặc hai hình vuông theo chiều dọc và một hình vuông theo chiều ngang.

Vì vậy, nếu đầu vào giống như r =6, c =1, thì đầu ra sẽ là 3, màu đỏ là vị trí ban đầu, màu xanh lá cây là cuối cùng và màu vàng là các bước trung gian.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu r
• hoán đổi r và c

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

6, 1

Đầu ra

3