{"id":9250,"date":"2021-12-26T01:55:53","date_gmt":"2021-12-26T09:55:53","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9250"},"modified":"2021-12-26T03:27:31","modified_gmt":"2021-12-26T11:27:31","slug":"leetcode-2120-execution-of-all-suffix-instructions-staying-in-a-grid","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/uncategorized\/leetcode-2120-execution-of-all-suffix-instructions-staying-in-a-grid\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2120. Execution of All Suffix Instructions Staying in a Grid"},"content":{"rendered":"\n<p>There is an&nbsp;<code>n x n<\/code>&nbsp;grid, with the top-left cell at&nbsp;<code>(0, 0)<\/code>&nbsp;and the bottom-right cell at&nbsp;<code>(n - 1, n - 1)<\/code>. You are given the integer&nbsp;<code>n<\/code>&nbsp;and an integer array&nbsp;<code>startPos<\/code>&nbsp;where&nbsp;<code>startPos = [start<sub>row<\/sub>, start<sub>col<\/sub>]<\/code>&nbsp;indicates that a robot is initially at cell&nbsp;<code>(start<sub>row<\/sub>, start<sub>col<\/sub>)<\/code>.<\/p>\n\n\n\n<p>You are also given a&nbsp;<strong>0-indexed<\/strong>&nbsp;string&nbsp;<code>s<\/code>&nbsp;of length&nbsp;<code>m<\/code>&nbsp;where&nbsp;<code>s[i]<\/code>&nbsp;is the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;instruction for the robot:&nbsp;<code>'L'<\/code>&nbsp;(move left),&nbsp;<code>'R'<\/code>&nbsp;(move right),&nbsp;<code>'U'<\/code>&nbsp;(move up), and&nbsp;<code>'D'<\/code>&nbsp;(move down).<\/p>\n\n\n\n<p>The robot can begin executing from any&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;instruction in&nbsp;<code>s<\/code>. It executes the instructions one by one towards the end of&nbsp;<code>s<\/code>&nbsp;but it stops if either of these conditions is met:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The next instruction will move the robot off the grid.<\/li><li>There are no more instructions left to execute.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>an array<\/em>&nbsp;<code>answer<\/code>&nbsp;<em>of length<\/em>&nbsp;<code>m<\/code>&nbsp;<em>where<\/em>&nbsp;<code>answer[i]<\/code>&nbsp;<em>is&nbsp;<strong>the number of instructions<\/strong>&nbsp;the robot can execute if the robot&nbsp;<strong>begins executing from<\/strong>&nbsp;the<\/em>&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;<em>instruction in<\/em>&nbsp;<code>s<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/12\/09\/1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 3, startPos = [0,1], s = \"RRDDLU\"\n<strong>Output:<\/strong> [1,5,4,3,1,0]\n<strong>Explanation:<\/strong> Starting from startPos and beginning execution from the i<sup>th<\/sup> instruction:\n- 0<sup>th<\/sup>: \"<strong>R<\/strong>RDDLU\". Only one instruction \"R\" can be executed before it moves off the grid.\n- 1<sup>st<\/sup>:  \"<strong>RDDLU<\/strong>\". All five instructions can be executed while it stays in the grid and ends at (1, 1).\n- 2<sup>nd<\/sup>:   \"<strong>DDLU<\/strong>\". All four instructions can be executed while it stays in the grid and ends at (1, 0).\n- 3<sup>rd<\/sup>:    \"<strong>DLU<\/strong>\". All three instructions can be executed while it stays in the grid and ends at (0, 0).\n- 4<sup>th<\/sup>:     \"<strong>L<\/strong>U\". Only one instruction \"L\" can be executed before it moves off the grid.\n- 5<sup>th<\/sup>:      \"U\". If moving up, it would move off the grid.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/12\/09\/2.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 2, startPos = [1,1], s = \"LURD\"\n<strong>Output:<\/strong> [4,1,0,0]\n<strong>Explanation:<\/strong>\n- 0<sup>th<\/sup>: \"<strong>LURD<\/strong>\".\n- 1<sup>st<\/sup>:  \"<strong>U<\/strong>RD\".\n- 2<sup>nd<\/sup>:   \"RD\".\n- 3<sup>rd<\/sup>:    \"D\".\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/12\/09\/3.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 1, startPos = [0,0], s = \"LRUD\"\n<strong>Output:<\/strong> [0,0,0,0]\n<strong>Explanation:<\/strong> No matter which instruction the robot begins execution from, it would move off the grid.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>m == s.length<\/code><\/li><li><code>1 &lt;= n, m &lt;= 500<\/code><\/li><li><code>startPos.length == 2<\/code><\/li><li><code>0 &lt;= start<sub>row<\/sub>, start<sub>col<\/sub>&nbsp;&lt; n<\/code><\/li><li><code>s<\/code>&nbsp;consists of&nbsp;<code>'L'<\/code>,&nbsp;<code>'R'<\/code>,&nbsp;<code>'U'<\/code>, and&nbsp;<code>'D'<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Simulation<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(m<sup>2<\/sup>)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<int> executeInstructions(int n, vector<int>& startPos, string s) {\n    const int m = s.length();\n    auto moves = [&](int k) -> int {\n      int x = startPos[1];\n      int y = startPos[0];\n      for (int i = k; i < m; ++i) {\n        switch (s[i]) {\n          case 'R': x += 1; break;\n          case 'D': y += 1; break;\n          case 'L': x -= 1; break;\n          case 'U': y -= 1; break;\n        }        \n        if (x < 0 || x == n || y < 0 || y == n) \n          return i - k;\n      }\n      return m - k;\n    };\n    vector<int> ans(m);\n    for (int i = 0; i < m; ++i)\n      ans[i] = moves(i);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>There is an&nbsp;n x n&nbsp;grid, with the top-left cell at&nbsp;(0, 0)&nbsp;and the bottom-right cell at&nbsp;(n &#8211; 1, n &#8211; 1). You are given the integer&nbsp;n&nbsp;and&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-9250","post","type-post","status-publish","format-standard","hentry","category-uncategorized","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9250","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=9250"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9250\/revisions"}],"predecessor-version":[{"id":9252,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9250\/revisions\/9252"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9250"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9250"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9250"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}