C++ | Easy | 2 approaches ( BFS && Manhattan Distance )
Using Manhattan Distance\nIt is quite intuitive to use this distance ( which is basically the time taken to reach from any point to other point ( target ) ) . T
1. Using Manhattan Distance\nIt is quite intuitive to use this distance ( which is basically the time taken to reach from any point to other point ( target ) ) . The intuition being that if ghosts can reach the target from any coordinates in ghosts array before or at the same time as you, then you return false. Else, return true;\n\n```\nclass Solution {\npublic:\n    bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {\n        int timeTakenByMe = abs(target[0]) + abs(target[1]);\n        int timeTakenByGhost = INT_MAX;\n        \n        int n = ghosts.size();\n        for(int i = 0;i<n;i++)\n        {\n            int x = ghosts[i][0];\n            int y = ghosts[i][1];\n            timeTakenByGhost = min (timeTakenByGhost, abs(x - target[0]) + abs(y - target[1]));\n        }\n\n        return timeTakenByMe < timeTakenByGhost;\n    }\n};\n```\n\n2. Calculating distance using BFS (although it gives TLE)\n```\nstruct Node\n{\n  int x,y,dist;\n    Node(int x,int y,int dist)\n    {\n        this->x = x;\n        this->y = y;\n        this->dist = dist;\n    }\n};\nclass Solution {\npublic:\n    bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {\n        int timeTakenByMe = abs(target[0]) + abs(target[1]);\n        \n        queue<Node> q;\n        int n = ghosts.size();\n        map<pair<int,int>,int> vis;\n        for(int i = 0;i<n;i++)\n        {\n            int x = ghosts[i][0];\n            int y = ghosts[i][1];\n            q.push(Node(x,y,0));\n        }\n        int dx[] = {0,0,1,-1};\n        int dy[] = {1,-1,0,0};\n        while(!q.empty())\n        {\n            int sz = q.size();\n            for(int i = 0;i<sz;i++)\n            {\n                int x = q.front().x;\n                int y = q.front().y;\n                int dist = q.front().dist;\n                q.pop();\n                \n                if(dist > timeTakenByMe)\n                    return true;\n                \n                if(!vis[{x,y}])\n                {\n                    if(x == target[0] && y == target[1])\n                    {\n                        return timeTakenByMe < dist;\n                    }\n                    vis[{x,y}] = 1;    \n                    \n                    for(int k =0;k<4;k++)\n                    {\n                        int newx = x + dx[k];\n                        int newy = y + dy[k];\n                        \n                        if(!vis[{newx,newy}])\n                        {\n                            q.push(Node(newx,newy,dist + 1));\n                        }\n                    }\n                }\n            }\n        }\n        return false;\n    }\n};\n```
['Math', 'Breadth-First Search', 'C']