{"id":1861,"date":"2018-02-24T20:14:04","date_gmt":"2018-02-25T04:14:04","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1861"},"modified":"2018-03-04T10:42:33","modified_gmt":"2018-03-04T18:42:33","slug":"leetcode-789-escape-the-ghosts","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-789-escape-the-ghosts\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 789. Escape The Ghosts"},"content":{"rendered":"

\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u76ee\u7684\u5730\u5750\u6807\u4ee5\u53ca\u5e7d\u7075\u7684\u5750\u6807\uff0c\u521d\u59cb\u70b9\u5728(0,0)\uff0c\u6bcf\u6b21\u4f60\u548c\u5e7d\u7075\u90fd\u53ef\u4ee5\u79fb\u52a8\u4e00\u6b65\u3002\u95ee\u4f60\u662f\u5426\u53ef\u4ee5\u5b89\u5168\u5230\u8fbe\u7ec8\u70b9\u3002<\/p>\n

You are playing a simplified Pacman game. You\u00a0start at the point\u00a0(0, 0)<\/code>, and your destination is\u00a0(target[0], target[1])<\/code>. There are several ghosts on the map, the i-th ghost starts at\u00a0(ghosts[i][0], ghosts[i][1])<\/code>.<\/p>\n

Each turn, you and all ghosts simultaneously *may* move in one of 4 cardinal directions: north, east, west, or south, going from the previous point to a new point 1 unit of distance away.<\/p>\n

You escape if and only if you can reach the target before any ghost reaches you (for any given moves the ghosts may take.)\u00a0 If you reach any square (including the target) at the same time as a ghost, it doesn’t count as an escape.<\/p>\n

Return True if and only if it is possible to escape.<\/p>\n

Example 1:\r\nInput: \r\nghosts = [[1, 0], [0, 3]]\r\ntarget = [0, 1]\r\nOutput: true\r\nExplanation: \r\nYou can directly reach the destination (0, 1) at time 1, while the ghosts located at (1, 0) or (0, 3) have no way to catch up with you.\r\n<\/pre>\n
Example 2:\r\nInput: \r\nghosts = [[1, 0]]\r\ntarget = [2, 0]\r\nOutput: false\r\nExplanation: \r\nYou need to reach the destination (2, 0), but the ghost at (1, 0) lies between you and the destination.\r\n<\/pre>\n
Example 3:\r\nInput: \r\nghosts = [[2, 0]]\r\ntarget = [1, 0]\r\nOutput: false\r\nExplanation: \r\nThe ghost can reach the target at the same time as you.\r\n<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  • All points have coordinates with absolute value <=\u00a010000<\/code>.<\/li>\n
  • The number of ghosts will not exceed\u00a0100<\/code>.<\/li>\n<\/ul>\n
    Solution: Greedy \/ Math<\/strong><\/p>\n
    You can escape if and only if no ghosts can reach target before you. Just need to compare the Manhattan distance.<\/p>\n
    \u5982\u679c\u6240\u6709\u7684\u5e7d\u7075\u90fd\u65e0\u6cd5\u5728\u4f60\u4e4b\u524d\u5230\u8fbetarget\uff0c\u90a3\u4e48\u4f60\u53ef\u4ee5\u9003\u8131\u3002\u53ea\u8981\u6bd4\u8f83\u66fc\u54c8\u987f\u8ddd\u79bb\u5373\u53ef\u3002<\/p>\n
    C++<\/p>\n
    Time complexity: O(|ghost|)<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 4 ms\r\nclass Solution {\r\npublic:\r\n  bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {\r\n    const int steps = abs(target[0]) + abs(target[1]);\r\n    for (const auto& g: ghosts)\r\n      if (abs(g[0] - target[0]) + abs(g[1] - target[1]) <= steps) \r\n        return false;\r\n    return true;\r\n  }\r\n};<\/pre>\n
    Java<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 4 ms\r\nclass Solution {\r\n  public boolean escapeGhosts(int[][] ghosts, int[] target) {\r\n    final int steps = Math.abs(target[0]) + Math.abs(target[1]);\r\n    for (int[] g : ghosts) \r\n      if (Math.abs(g[0] - target[0]) + Math.abs(g[1] - target[1]) <= steps)\r\n        return false;    \r\n    return true;\r\n  }\r\n}<\/pre>\n
    Python3<\/p>\n
    \"\"\"\r\nAuthor: Huahua\r\nRunning time: 40 ms\r\n\"\"\"\r\nclass Solution:\r\n  def escapeGhosts(self, ghosts, target):\r\n    steps = abs(target[0]) + abs(target[1])\r\n    return not any(abs(x - target[0]) + abs(y - target[1]) <= steps for x, y in ghosts)<\/pre>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    \u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u76ee\u7684\u5730\u5750\u6807\u4ee5\u53ca\u5e7d\u7075\u7684\u5750\u6807\uff0c\u521d\u59cb\u70b9\u5728(0,0)\uff0c\u6bcf\u6b21\u4f60\u548c\u5e7d\u7075\u90fd\u53ef\u4ee5\u79fb\u52a8\u4e00\u6b65\u3002\u95ee\u4f60\u662f\u5426\u53ef\u4ee5\u5b89\u5168\u5230\u8fbe\u7ec8\u70b9\u3002 You are playing a simplified Pacman game. You\u00a0start at the point\u00a0(0, 0), and your destination is\u00a0(target[0], target[1]). There are several ghosts on the map,…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[88,31,177],"class_list":["post-1861","post","type-post","status-publish","format-standard","hentry","category-math","tag-greedy","tag-math","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1861","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=1861"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1861\/revisions"}],"predecessor-version":[{"id":1892,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1861\/revisions\/1892"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1861"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1861"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1861"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}