{"id":8693,"date":"2021-11-13T20:30:16","date_gmt":"2021-11-14T04:30:16","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8693"},"modified":"2021-11-13T20:35:08","modified_gmt":"2021-11-14T04:35:08","slug":"leetcode-2069-walking-robot-simulation-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-2069-walking-robot-simulation-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2069. Walking Robot Simulation II"},"content":{"rendered":"\n

A width x height<\/code> grid is on an XY-plane with the bottom-left<\/strong> cell at (0, 0)<\/code> and the top-right<\/strong> cell at (width - 1, height - 1)<\/code>. The grid is aligned with the four cardinal directions (\"North\"<\/code>, \"East\"<\/code>, \"South\"<\/code>, and \"West\"<\/code>). A robot is initially<\/strong> at cell (0, 0)<\/code> facing direction \"East\"<\/code>.<\/p>\n\n\n\n

The robot can be instructed to move for a specific number of steps<\/strong>. For each step, it does the following.<\/p>\n\n\n\n

  1. Attempts to move forward one<\/strong> cell in the direction it is facing.<\/li>
  2. If the cell the robot is moving to<\/strong> is out of bounds<\/strong>, the robot instead turns<\/strong> 90 degrees counterclockwise<\/strong> and retries the step.<\/li><\/ol>\n\n\n\n

    After the robot finishes moving the number of steps required, it stops and awaits the next instruction.<\/p>\n\n\n\n

    Implement the Robot<\/code> class:<\/p>\n\n\n\n

    • Robot(int width, int height)<\/code> Initializes the width x height<\/code> grid with the robot at (0, 0)<\/code> facing \"East\"<\/code>.<\/li>
    • void move(int num)<\/code> Instructs the robot to move forward num<\/code> steps.<\/li>
    • int[] getPos()<\/code> Returns the current cell the robot is at, as an array of length 2, [x, y]<\/code>.<\/li>
    • String getDir()<\/code> Returns the current direction of the robot, \"North\"<\/code>, \"East\"<\/code>, \"South\"<\/code>, or \"West\"<\/code>.<\/li><\/ul>\n\n\n\n

      Example 1:<\/strong><\/p>\n\n\n\n

      \"example-1\"\/<\/figure>\n\n\n\n
      Input<\/strong>\n[\"Robot\", \"move\", \"move\", \"getPos\", \"getDir\", \"move\", \"move\", \"move\", \"getPos\", \"getDir\"]\n[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]\nOutput<\/strong>\n[null, null, null, [4, 0], \"East\", null, null, null, [1, 2], \"West\"]\n\nExplanation<\/strong>\nRobot robot = new Robot(6, 3); \/\/ Initialize the grid and the robot at (0, 0) facing East.\nrobot.move(2);  \/\/ It moves two steps East to (2, 0), and faces East.\nrobot.move(2);  \/\/ It moves two steps East to (4, 0), and faces East.\nrobot.getPos(); \/\/ return [4, 0]\nrobot.getDir(); \/\/ return \"East\"\nrobot.move(2);  \/\/ It moves one step East to (5, 0), and faces East.\n                \/\/ Moving the next step East would be out of bounds, so it turns and faces North.\n                \/\/ Then, it moves one step North to (5, 1), and faces North.\nrobot.move(1);  \/\/ It moves one step North to (5, 2), and faces North<\/strong> (not West).\nrobot.move(4);  \/\/ Moving the next step North would be out of bounds, so it turns and faces West.\n                \/\/ Then, it moves four steps West to (1, 2), and faces West.\nrobot.getPos(); \/\/ return [1, 2]\nrobot.getDir(); \/\/ return \"West\"\n\n<\/pre>\n\n\n\n
      Constraints:<\/strong><\/p>\n\n\n\n
      • 2 <= width, height <= 100<\/code><\/li>
      • 1 <= num <= 105<\/sup><\/code><\/li>
      • At most 104<\/sup><\/code> calls in total<\/strong> will be made to move<\/code>, getPos<\/code>, and getDir<\/code>.<\/li><\/ul>\n\n\n\n
        Solution: Simulation<\/strong><\/h2>\n\n\n\n
        Note num >> w + h, when we hit a wall, we will always follow the boundary afterwards. We can do num %= p to reduce steps, where p = ((w – 1) + (h – 1)) * 2<\/p>\n\n\n\n
        Time complexity: move: O(min(num, w+h))
        Space complexity: O(1)<\/p>\n\n\n\n
        \n
        C++<\/h2>\n
        \n\n
        \n\/\/ Author: Huahua\nconstexpr static int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};\nconst static vector kNames{\"East\", \"North\", \"West\", \"South\"};\n\nclass Robot {\npublic:\n  Robot(int width, int height): w_(width), h_(height) {\n    p_ = ((w_ - 1) + (h_ - 1)) * 2;\n  }\n\n  void move(int num) {    \n    while (num) {\n      int tx = x_ + dirs[d_][0];\n      int ty = y_ + dirs[d_][1];\n      if (tx < 0 || tx >= w_ || ty < 0 || ty >= h_) {\n        if (num > p_) num %= p_;\n        if (num) d_ = (d_ + 1) % 4;        \n        continue;\n      }\n      x_ = tx;\n      y_ = ty;\n      --num;\n    }    \n  }\n\n  vector getPos() { return {x_, y_}; }\n\n  string getDir() { return kNames[d_]; }\nprivate:  \n  int w_;\n  int h_;\n  int d_{0}; \/\/ 0: E, 1: N, 2: W, 3: S\n  int x_{0};\n  int y_{0};\n  int p_{0};\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
        A width x height grid is on an XY-plane with the bottom-left cell at (0, 0) and the top-right cell at (width – 1, height – 1). The grid is aligned with the four…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[177,179],"class_list":["post-8693","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-medium","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8693","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=8693"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8693\/revisions"}],"predecessor-version":[{"id":8697,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8693\/revisions\/8697"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8693"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8693"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8693"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}