ปัญหา: Squirrel Simulation
มีต้นไม้, หนูน้อย, และถั่วหลายเม็ด บนกริด 2D
หนูน้อยขนถั่วทีละเม็ด ไปวางที่ต้นไม้ เคลื่อนที่ 4 ทิศทาง หา ระยะทางรวมน้อยที่สุด
ตัวอย่าง
Height=5, Width=7, Tree=[2,2], Squirrel=[4,4], Nuts=[[3,0],[2,5]]
Output: 12
แนวทางแก้ปัญหา: Greedy Math
ข้อสังเกตสำคัญ
- ถ้าหนูเริ่มจากต้นไม้: แต่ละถั่วใช้ระยะ
2 × dist(tree, nut)(ไป-กลับ) - แต่หนูเริ่มจาก
squirrel→ ถั่วเม็ดแรก:dist(squirrel, nut) + dist(nut, tree) - ความต่าง (savings) =
2×dist(tree,nut) - (dist(squirrel,nut) + dist(nut,tree))=dist(tree,nut) - dist(squirrel,nut) - เลือกถั่วที่ savings มากที่สุด (หรือ diff น้อยที่สุด) เป็นเม็ดแรก
สูตร
total = Σ 2×dist(tree, nut_i) - max_savings
savings_i = dist(tree, nut_i) - dist(squirrel, nut_i)
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minDistance(int height, int width, vector<int>& tree,
vector<int>& squirrel, vector<vector<int>>& nuts) {
auto dist = [](int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
};
int total = 0;
int maxSave = INT_MIN;
for (auto& nut : nuts) {
int dTreeNut = dist(tree[0], tree[1], nut[0], nut[1]);
int dSquirrelNut = dist(squirrel[0], squirrel[1], nut[0], nut[1]);
total += 2 * dTreeNut;
maxSave = max(maxSave, dTreeNut - dSquirrelNut);
}
return total - maxSave;
}
};
int main() {
Solution ob;
vector<int> tree = {2,2}, squirrel = {4,4};
vector<vector<int>> nuts = {{3,0}, {2,5}};
cout << ob.minDistance(5, 7, tree, squirrel, nuts); // 12
return 0;
}
การคำนวณตัวอย่าง
Nut [3,0]: dist(tree)=|2-3|+|2-0|=3, dist(squirrel)=|4-3|+|4-0|=5 → 2×3=6, save=3-5=-2 Nut [2,5]: dist(tree)=|2-2|+|2-5|=3, dist(squirrel)=|4-2|+|4-5|=3 → 2×3=6, save=3-3=0 Total = 6+6=12, maxSave=0 → Answer = 12-0=12
ความซับซ้อน
- เวลา: O(N) – N = จำนวนถั่ว
- พื้นที่: O(1)
ข้อสังเกต
- LeetCode 573
- ไม่ต้อง simulate การเคลื่อนที่ – คำนวณทางคณิตศาสตร์ได้โดยตรง
- Manhattan distance ใช้เพราะเคลื่อนที่ 4 ทิศทางบนกริด
- maxSave อาจเป็นลบ (ถ้าหนูเริ่มไกลกว่าต้นไม้สำหรับทุกถั่ว) → ยังคงลบออกได้ (คือเพิ่มระยะทาง)
