# 2120. Execution of All Suffix Instructions Staying in a Grid
###### tags: `Leetcode` `Medium` `HashMap` `Simulation`
Link: https://leetcode.com/problems/execution-of-all-suffix-instructions-staying-in-a-grid/description/
## 思路
思路参考[这里](https://leetcode.com/problems/execution-of-all-suffix-instructions-staying-in-a-grid/solutions/1647617/python-o-m-solution-with-detailed-explanation/)

根据startPos我们可以知道 在不超过边界的情况下 我们最多可以向上/下/左/右移动几格
我们从后往前遍历并假设endPos是在[0,0]
我们把每个位置的currPos存进map
然后假设我们遍历到了位置```i```对于现在的currPos 如果前面遇到过有row=currPos-upMost或者currPos+downMost的说明在这两个位置中间的movement会超过边界
那么如果出现了多个currPos-upMost怎么办呢？显然是保留最近的那个

这时候可能会问 会不会在这一段中间的某个点出现超过边界的情况呢 答案是不会 因为距离是一点点加上去的 如果中间某个点的currRow小于currPos-upMost 那么在这之前一定会有一个点的currRow等于currPos-upMost
## Code
$O(N)$

class Solution:
    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:
        m = len(s)
        dirs = {'U':[-1,0],'D':[1,0],'L':[0,-1],'R':[0,1]}
        upMost = startPos[0]+1
        downMost = n-startPos[0]
        leftMost = startPos[1]+1
        rightMost = n-startPos[1]
        curr_row, curr_col = 0, 0
        next_row, next_col = {0:m}, {0:m}
        ans = []

        for i in range(m-1, -1, -1):
            curr_row -= dirs[s[i]][0]
            curr_col -= dirs[s[i]][1]
            maxstep = m-i
            
            if curr_row - upMost in next_row:  
                maxstep = min(maxstep,  next_row[curr_row - upMost] - i - 1)
            if curr_row + downMost in next_row:  
                maxstep = min(maxstep,  next_row[curr_row + downMost] - i - 1)
            if curr_col - leftMost in next_col:  
                maxstep = min(maxstep,  next_col[curr_col - leftMost] - i - 1)
            if curr_col + rightMost in next_col: 
                maxstep = min(maxstep,  next_col[curr_col + rightMost] - i - 1)

            next_row[curr_row] = i
            next_col[curr_col] = i
            ans.append(maxstep)
        
        return ans[::-1]

$O(N^2)$

class Solution:
    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:
        m = len(s)
        dirs = {'U':[-1,0],'D':[1,0],'L':[0,-1],'R':[0,1]}
        ans = []
        for i in range(len(s)):
            currRow, currCol = startPos[0], startPos[1]
            j = i
            for j in range(i, len(s)+1):
                if j==len(s): break
                currRow += dirs[s[j]][0]
                currCol += dirs[s[j]][1]
                if currRow<0 or currRow>=n or currCol<0 or currCol>=n:
                    break
            ans.append(j-i)
        return ans