กบข้ามแม่น้ำใน C++ (Frog Jump)

ภาพรวมปัญหา

กบอยากข้ามแม่น้ำ โดยกระโดดบนหินที่มีตำแหน่งกำหนด (เรียงจากน้อยไปมาก) กระโดดครั้งแรกต้องเป็น 1 หน่วย หากกระโดดครั้งก่อนเป็น k หน่วย ครั้งถัดไปต้องเป็น k-1, k, หรือ k+1 หน่วย เท่านั้น ตรวจสอบว่ากบข้ามไปหินสุดท้ายได้หรือไม่

ตัวอย่าง

stones = [0,1,3,5,6,8,12,17] → Output: true (1)

วิธีแก้ปัญหา: DFS + Memoization

ใช้ visited[key] เก็บผลลัพธ์ของสถานะ (pos, k) โดย key = pos | (k << 11)

ขั้นตอนหลัก

1. ฟังก์ชัน canCross(stones, pos, k):
   • ถ้า state นี้คำนวณแล้ว → คืนค่าทันที
   • วน i = pos+1 ถึง stones.size()-1:
     • gap = stones[i] - stones[pos]
     • ถ้า gap < k-1 → ข้าม (หินใกล้เกินไป)
     • ถ้า k+1 → หยุด (หินไกลเกินไป เพราะ stones เรียงแล้ว)
     • ถ้า canCross(stones, i, gap) เป็น true → คืน true
   • ถ้าไม่มีทางไหนได้ → บันทึก false และคืน false
   • กรณีฐาน: ถ้า → คืน true

โค้ด C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
    unordered_map<lli, int> visited;
    bool canCross(vector<int>& stones, int pos = 0, int k = 0) {
        lli key = pos | (k << 11);
        if (visited.find(key) != visited.end()) return visited[key];
        for (int i = pos + 1; i < stones.size(); i++) {
            int gap = stones[i] - stones[pos];
            if (gap < k - 1) continue;
            if (gap > k + 1) return visited[key] = false;
            if (canCross(stones, i, gap)) return visited[key] = true;
        }
        return visited[key] = (pos == stones.size() - 1);
    }
};

int main() {
    Solution ob;
    vector<int> v = {0,1,3,5,6,8,12,17};
    cout << (ob.canCross(v));
}

การวิเคราะห์ความซับซ้อน

• เวลา: O(n²) ในกรณีแย่ที่สุด (n = จำนวนหิน) แต่ Memoization ช่วยลดลงมาก
• พื้นที่: O(n²) สำหรับตาราง visited