Escape The Ghosts: หนีผีใน C++

ปัญหา

เล่น Pacman เริ่มที่ (0,0) เป้าหมาย target มีผีหลายตัวที่ ghosts[i] ทุกรอบเคลื่อนที่ 1 ช่อง (N/E/W/S) พร้อมกัน หนีได้ถ้าถึง Target ก่อน ผีทุกตัว (ถึงพร้อมกัน = แพ้) คืน True/False

ตัวอย่าง: ghosts=[[1,0],[0,3]], target=[0,1] → True (เราไป (0,1) ใช้ 1 Turn, ผีไปไม่ทัน)

ข้อสังเกตสำคัญ

Manhattan Distance = จำนวน Turn ขั้นต่ำในการเดินทาง

• เรา: myDist = |target.x| + |target.y|
• ผี i: ghostDist = |ghost.x - target.x| + |ghost.y - target.y|

เราหนีได้ ⟺ myDist < ghostDist สำหรับทุกผี

เหตุผล: ผีเดิน Optimal ได้ Manhattan Distance เช่นเดียวกัน หากผีใดมีระยะทาง ≤ เรา → ผีสามารถมาถึง Target ก่อนหรือพร้อมเรา

โค้ด C++

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

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

int main() {
    Solution ob;
    vector<vector<int>> ghosts = {{1,0}, {0,3}};
    vector<int> target = {0,1};
    cout << ob.escapeGhosts(ghosts, target);  // 1 (true)
    return 0;
}

ความซับซ้อน

• Time: O(g) - g = จำนวนผี
• Space: O(1)

Input / Output

Input:  [[1,0],[0,3]] [0,1]
Output: 1 (true)