Final Grid Position Under Timestamped Direction Changes With Dot Obstacles

An object sits on a rectangular grid. Over time, a list of timestamped actions sets the direction in which it travels: up, down, left or right. While a direction is set, the object moves one cell per time unit in that direction for as long as the next cell is open. When the next cell is blocked or outside the grid, the object waits in place until a later action changes its direction.

Given the grid, the starting cell, the actions and an end time, return the cell the object occupies at the end time.

Read the grid legend carefully: a dot '.' marks a blocked cell that the object can never enter, and 'o' marks an open cell.

Function Signature

def final_position(grid: list[str], start: list[int], actions: list[tuple[int, str]], end_time: int) -> list[int]:

start is [row, col]. Each action is (time, direction).

Rules

• grid[r][c] is 'o' for an open cell and '.' for a blocked cell.
• Row 0 is the top row and column 0 is the leftmost column. From (row, col), "up" leads to (row - 1, col), "down" to (row + 1, col), "left" to (row, col - 1) and "right" to (row, col + 1).
• The object is at rest from time 0 until the first action. An action (t, d) sets the direction to d at time t, and that direction stays in effect until the next action.
• Time advances in whole units. For each unit s = 0, 1, ..., end_time - 1, the direction during that unit is the one set by the last action with time <= s; if there is no such action, the object does not move during that unit. If a direction is set and the neighboring cell in that direction is inside the grid and open, the object moves into it at the end of the unit. Otherwise it stays where it is.
• Cells outside the grid behave like blocked cells, so the object never leaves the grid.
• Actions with time >= end_time have no effect.
• Return the object's cell [row, col] at time end_time. If end_time is 0, this is start.

Constraints

• 1 <= len(grid) <= 500 and 1 <= len(grid[0]) <= 500; all rows have the same length, and every character is 'o' or '.'.
• start is an open cell inside the grid.
• 0 <= len(actions) <= 10^5
• 0 <= time <= 10^9 for every action, and action times are strictly increasing.
• Every direction is one of "up", "down", "left" and "right".
• 0 <= end_time <= 10^9

Examples

Example 1

Input: grid = ["ooooo", "o.o.o", "ooooo"], start = [0, 0],
 actions = [(0, "right"), (3, "down"), (5, "left")], end_time = 7
Output: [0, 1]

During units 0 to 2 the object moves right to (0, 3). From unit 3 the direction is down, but (1, 3) is a dot, so it is blocked and the object waits during units 3 and 4. During units 5 and 6 it moves left to (0, 2) and then (0, 1).

Example 2

Input: grid = ["ooooo", "o.o.o", "ooooo"], start = [2, 4],
 actions = [(2, "left"), (4, "up"), (50, "right")], end_time = 60
Output: [0, 4]

Units 0 and 1 have no direction, so the object stays at (2, 4). During units 2 and 3 it moves left to (2, 2). From unit 4 it moves up through the open cell (1, 2) to (0, 2), and from unit 6 the top edge stops it. From unit 50 it moves right to (0, 3) and (0, 4), and the right edge stops it from unit 52 until the end.

Example 3

Input: grid = ["ooo"], start = [0, 2],
 actions = [(0, "left"), (1, "right"), (3, "left")], end_time = 3
Output: [0, 2]

During unit 0 the object moves left to (0, 1). During unit 1 it moves right back to (0, 2). During unit 2 the edge of the grid blocks it. The action at time 3 is not before end_time, so it has no effect.