Thoát khỏi ma (Escape The Ghosts) C++

Pacman đơn giản: start (0,0), target (tx,ty). Ma tại ghosts[i]. Mỗi lượt di chuyển 1 bước 4 hướng. Thoát nếu đến target trước mọi ma (cùng lúc không tính). Trả về true/false.

Ví dụ

Input - ghosts=[[1,0],[0,3]], target=[0,1] Output - true

Giải thích - Pacman đến (0,1) sau 1 bước. Ma tại (1,0) cần ≥2 bước, ma (0,3) cần ≥2 bước.

Phương pháp tiếp cận

• Khoảng cách Manhattan: me = |tx| + |ty|
• Với mỗi ma: dist = |gx-tx| + |gy-ty|
• Nếu bất kỳ ma nào có dist ≤ me → false (ma đến trước hoặc cùng lúc)
• Ngược lại → true

Ví dụ code C++

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

class Solution {
public:
    bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
        int me = abs(target[0]) + abs(target[1]);
        for (auto& g : ghosts) {
            int dist = abs(g[0] - target[0]) + abs(g[1] - target[1]);
            if (dist <= me) return false;
        }
        return true;
    }
};

int main() {
    vector<vector<int>> v1 = {{1,0}, {0,3}};
    vector<int> v2 = {0,1};
    Solution ob;
    cout << ob.escapeGhosts(v1, v2);
    return 0;
}

Kết quả

1