Chương trình tìm số bước tối thiểu của mã ngựa đến vị trí mục tiêu trong Python

Mô tả bài toán

Mã ngựa bắt đầu tại (0,0) trên bàn cờ vô hạn. Tìm số bước tối thiểu để đến (r,c). Mã đi theo chữ L: 2 ô theo một hướng, 1 ô theo hướng vuông góc.

Ví dụ: r=6, c=1 → đầu ra 3.

Giải thuật (Công thức toán học)

1. Đảm bảo r >= c (hoán đổi nếu cần).
2. Trường hợp đặc biệt: (1,0) → 3; (2,2) → 4.
3. delta = r - c.
4. Nếu c > delta: trả về delta - 2 * ((delta - c) // 3).
5. Ngược lại: trả về delta - 2 * ((delta - c) // 4).

Ví dụ mã Python

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