โปรแกรมหาขั้นตอนน้อยสุดของม้าไปยังเป้าหมายใน Python

สมมติว่ามีพิกัด r, c ม้าอยู่ที่ (0,0) บนกระดานอันิเมต ต้องการหาขั้นตอนน้อยสุดไป (r,c)

ตัวอย่าง: r=6, c=1 ผลลัพธ์ 3

ขั้นตอนการแก้ปัญหา

1. ถ้า r < c: สลับ
2. กรณีพิเศษ: (1,0) คืน 3, (2,2) คืน 4
3. delta = r - c
4. ถ้า c > delta: คืน delta - 2 * ((delta - c) // 3)
5. มิฉะนั้น: คืน delta - 2 * ((delta - c) // 4)

ตัวอย่างโค้ด

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