Mô phỏng sóc trong C++

Giới thiệu

Có cây, sóc, và các quả óc chó trên lưới 2D. Sóc di chuyển 4 hướng, mỗi lần chỉ mang 1 quả. Tìm tổng khoảng cách tối thiểu để sóc mang tất cả quả về cây.

Quan sát quan trọng

Tổng quãng đường nếu sóc bắt đầu từ cây: 2 * sum(dist(tree, nut_i)) (đi về lấy, mang về). Nhưng sóc bắt đầu từ vị trí sq. Nếu sóc đi lấy quả i trước, tiết kiệm được: dist(tree, nut_i) - dist(sq, nut_i). Chọn quả có tiết kiệm lớn nhất (hoặc chi phí thêm nhỏ nhất) làm quả đầu tiên.

Công thức

total = 2 * sum(dist(tree, nut_i))
maxSave = max_i [ dist(tree, nut_i) - dist(sq, nut_i) ]
answer = total - maxSave

Cài đặt C++

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

class Solution {
    int dist(vector& a, vector& b) {
        return abs(a[0]-b[0]) + abs(a[1]-b[1]);
    }
public:
    int minDistance(int height, int width, vector& tree, vector& sq, vector>& nuts) {
        int total = 0, maxSave = INT_MIN;
        for (auto& nut : nuts) {
            int dTree = dist(tree, nut);
            total += 2 * dTree;
            int dSq = dist(sq, nut);
            maxSave = max(maxSave, dTree - dSq);
        }
        return total - maxSave;
    }
};

int main() {
    Solution ob;
    vector tree = {2,2}, sq = {4,4};
    vector> nuts = {{3,0}, {2,5}};
    cout << ob.minDistance(5, 7, tree, sq, nuts); // Output: 12
    return 0;
}

Phân tích

• Thời gian: O(N) – N = số quả óc chó.
• Không gian: O(1).

LeetCode 573 "Squirrel Simulation".