execution-of-all-suffix-instructions-staying-in-a-grid

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

There is an <code>n x n</code> grid, with the top-left cell at <code>(0, 0)</code> and the bottom-right cell at <code>(n - 1, n - 1)</code>. You are given the integer <code>n</code> and an integer array <code>startPos</code> where <code>startPos = [startrow, startcol]</code> indicates that a robot is initially at cell <code>(startrow, startcol)</code>.

You are also given a 0-indexed string <code>s</code> of length <code>m</code> where <code>s[i]</code> is the <code>ith</code> instruction for the robot: <code>&#39;L&#39;</code> (move left), <code>&#39;R&#39;</code> (move right), <code>&#39;U&#39;</code> (move up), and <code>&#39;D&#39;</code> (move down).

The robot can begin executing from any <code>ith</code> instruction in <code>s</code>. It executes the instructions one by one towards the end of <code>s</code> but it stops if either of these conditions is met:

<ul>
	<li>The next instruction will move the robot off the grid.</li>
	<li>There are no more instructions left to execute.</li>
</ul>

Return an array <code>answer</code> of length <code>m</code> where <code>answer[i]</code> is the number of instructions the robot can execute if the robot begins executing from the <code>ith</code> instruction in <code>s</code>.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/09/1.png" style="width: 145px; height: 142px;" />
<pre>
Input: n = 3, startPos = [0,1], s = &quot;RRDDLU&quot;
Output: [1,5,4,3,1,0]
Explanation: Starting from startPos and beginning execution from the ith instruction:
- 0th: &quot;RRDDLU&quot;. Only one instruction &quot;R&quot; can be executed before it moves off the grid.
- 1st: &quot;RDDLU&quot;. All five instructions can be executed while it stays in the grid and ends at (1, 1).
- 2nd: &quot;DDLU&quot;. All four instructions can be executed while it stays in the grid and ends at (1, 0).
- 3rd: &quot;DLU&quot;. All three instructions can be executed while it stays in the grid and ends at (0, 0).
- 4th: &quot;LU&quot;. Only one instruction &quot;L&quot; can be executed before it moves off the grid.
- 5th: &quot;U&quot;. If moving up, it would move off the grid.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/09/2.png" style="width: 106px; height: 103px;" />
<pre>
Input: n = 2, startPos = [1,1], s = &quot;LURD&quot;
Output: [4,1,0,0]
Explanation:
- 0th: &quot;LURD&quot;.
- 1st: &quot;URD&quot;.
- 2nd: &quot;RD&quot;.
- 3rd: &quot;D&quot;.
</pre>

Example 3:
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/09/3.png" style="width: 67px; height: 64px;" />
<pre>
Input: n = 1, startPos = [0,0], s = &quot;LRUD&quot;
Output: [0,0,0,0]
Explanation: No matter which instruction the robot begins execution from, it would move off the grid.
</pre>

&nbsp;
Constraints:

<ul>
	<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;= startrow, startcol &lt; n</code></li>
	<li><code>s</code> consists of <code>&#39;L&#39;</code>, <code>&#39;R&#39;</code>, <code>&#39;U&#39;</code>, and <code>&#39;D&#39;</code>.</li>
</ul>

executeInstructions

Execution of All Suffix Instructions Staying in a Grid

Out of Boundary Paths

out-of-boundary-paths

出界的路径数

Robot Return to Origin

robot-return-to-origin

机器人能否返回原点

String

Simulation

现有一个 <code>n x n</code> 大小的网格，左上角单元格坐标 <code>(0, 0)</code> ，右下角单元格坐标 <code>(n - 1, n - 1)</code> 。给你整数 <code>n</code> 和一个整数数组 <code>startPos</code> ，其中 <code>startPos = [startrow, startcol]</code> 表示机器人最开始在坐标为 <code>(startrow, startcol)</code> 的单元格上。

另给你一个长度为 <code>m</code> 、下标从 0 开始的字符串 <code>s</code> ，其中 <code>s[i]</code> 是对机器人的第 <code>i</code> 条指令：<code>'L'</code>（向左移动），<code>'R'</code>（向右移动），<code>'U'</code>（向上移动）和 <code>'D'</code>（向下移动）。

机器人可以从 <code>s</code> 中的任一第 <code>i</code> 条指令开始执行。它将会逐条执行指令直到 <code>s</code> 的末尾，但在满足下述条件之一时，机器人将会停止：

<ul>
	<li>下一条指令将会导致机器人移动到网格外。</li>
	<li>没有指令可以执行。</li>
</ul>

返回一个长度为 <code>m</code> 的数组 <code>answer</code> ，其中 <code>answer[i]</code> 是机器人从第 <code>i</code>&nbsp;条指令 开始&nbsp;，可以执行的 指令数目 。

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2021/12/09/1.png" style="width: 145px; height: 142px;" />

<pre>
输入：n = 3, startPos = [0,1], s = "RRDDLU"
输出：[1,5,4,3,1,0]
解释：机器人从 startPos 出发，并从第 i 条指令开始执行：
- 0: "RRDDLU" 在移动到网格外之前，只能执行一条 "R" 指令。
- 1: "RDDLU" 可以执行全部五条指令，机器人仍在网格内，最终到达 (0, 0) 。
- 2: "DDLU" 可以执行全部四条指令，机器人仍在网格内，最终到达 (0, 0) 。
- 3: "DLU" 可以执行全部三条指令，机器人仍在网格内，最终到达 (0, 0) 。
- 4: "LU" 在移动到网格外之前，只能执行一条 "L" 指令。
- 5: "U" 如果向上移动，将会移动到网格外。
</pre>

示例 2：

<img alt="" src="https://assets.leetcode.com/uploads/2021/12/09/2.png" style="width: 106px; height: 103px;" />

<pre>
输入：n = 2, startPos = [1,1], s = "LURD"
输出：[4,1,0,0]
解释：
- 0: "LURD"
- 1: "URD"
- 2: "RD"
- 3: "D"
</pre>

示例 3：

<img alt="" src="https://assets.leetcode.com/uploads/2021/12/09/3.png" style="width: 67px; height: 64px;" />

<pre>
输入：n = 1, startPos = [0,0], s = "LRUD"
输出：[0,0,0,0]
解释：无论机器人从哪条指令开始执行，都会移动到网格外。
</pre>

&nbsp;

提示：

<ul>
	<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;= startrow, startcol &lt; n</code></li>
	<li><code>s</code> 由 <code>'L'</code>、<code>'R'</code>、<code>'U'</code> 和 <code>'D'</code> 组成</li>
</ul>