Minimum Knight Moves ใน C++ : หาจำนวนขั้นตอนน้อยที่สุดของ Knight บนกระดานหมากรุกอนันต์

โจทย์: กระดานหมากรุกขนาดอนันต์ (-∞ ถึง +∞) Knight เริ่มที่ [0, 0] หา **จำนวนขั้นตอนน้อยที่สุด** เพื่อไปถึง [x, y] (รับประกันว่ามีคำตอบ)

Knight เดินได้ 8 ทิศ: (±2, ±1) และ (±1, ±2)

ตัวอย่าง

x = 5, y = 5 -> Output: 4

Path: [0,0] → [2,1] → [4,2] → [3,4] → [5,5]

แนวทาง: DFS + Memoization (DP บน Grid)

เนื่องจากกระดานอเนกประสงค์ และ Knight เดินแบบ Symmetric เราสามารถ **Normalize** พิกัดให้อยู่ใน Quadrant I (x ≥ 0, y ≥ 0) และ x ≥ y ได้ (Swap ถ้าจำเป็น) แต่โค้ดตัวอย่างใช้แค่ abs()

Define dp[(x,y)] = Min steps จาก (0,0) ถึง (x,y)

Recurrence:

solve(x, y) = 1 + min( solve(|x-1|, |y-2|), solve(|x-2|, |y-1|) )

Base Cases:

• x + y == 0 -> 0 (อยู่ที่เป้าหมายแล้ว)
• x + y == 2 -> 2 (กรณีพิเศษ: (1,1), (2,0), (0,2) ต้องใช้ 2 ขั้น)

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

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    map<pair<int, int>, int> dp; // Memoization

    int solve(int x, int y) {
        if (x + y == 0) return 0;
        if (x + y == 2) return 2; // Special cases: (1,1), (2,0), (0,2)

        pair<int, int> key = {x, y};
        if (dp.count(key)) return dp[key];

        // Recurse to two possible previous positions
        return dp[key] = min(
            solve(abs(x - 1), abs(y - 2)),
            solve(abs(x - 2), abs(y - 1))
        ) + 1;
    }

    int minKnightMoves(int x, int y) {
        return solve(abs(x), abs(y)); // Normalize to quadrant I
    }
};

Input / Output

Input:  5 5
Output: 4

ความซับซ้อน (Complexity)

• Time: O(|x| * |y|) ในทางปฏิบัติ เนื่องจาก Memoization แต่ State Space จำกัดเพราะ Symmetry
• Space: O(|x| * |y|) สำหรับ DP Table

หมายเหตุเพิ่มเติม

มีสูตรทางคณิตศาสตร์ (Math Formula) ให้คำตอบ O(1) แต่ซับซ้อน วิธี DP + Recursion นี้เข้าใจง่าย พอสำหรับ Constraints ปกติ (|x|,|y| ≤ 300) และเป็นแนวคิด DP/BFS มาตรฐานครับ