Show problems as
Classic problem #874MediumArrayHash TableSimulation

Walking Robot Simulation

Real-world version: Sweeper Drone Sortie
Tracked in this browser only
Read Walking Robot Simulation on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A floor-sweeping drone sits on its charging pad at cell (0, 0) of a warehouse floor that stretches away without limit in every direction. It begins the sortie facing north, the direction in which y grows.

The drone works through moves in order. Each entry is one of the following:

  • -2: pivot a quarter turn to its left without leaving the cell it is on;
  • -1: pivot a quarter turn to its right without leaving the cell it is on;
  • a value k between 1 and 9: creep k cells straight ahead, one cell per step.

pillars[i] = [x, y] marks a cell taken up by a roof pillar. Before each single-cell step the drone looks at the cell directly ahead: if a pillar stands there it stays where it is and gives up the rest of that entry, but it still carries out every entry that follows.

Return the largest value of x * x + y * y over every cell the drone occupies during the sortie, where (x, y) is the cell.

Examples

Example 1

Input
moves = [2, -1, 6], pillars = [[0, 2]]
Output
37

The drone steps north to (0, 1), finds the pillar ahead and gives up that entry, pivots right to face east, then creeps to (6, 1), where 6 * 6 + 1 * 1 = 37.

Example 2

Input
moves = [5, -2, -2, 3], pillars = []
Output
25

The drone reaches (0, 5) with nothing in the way, then two left pivots turn it to face south and it comes back to (0, 2); the furthest cell it occupied was (0, 5).

Example 3

Input
moves = [-2, 5, -1, 3], pillars = [[-3, 0], [2, 2]]
Output
13

Facing west the drone halts at (-2, 0) with the pillar at (-3, 0) ahead of it, then pivots back to north and finishes at (-2, 3), where 4 + 9 = 13.

Constraints

  • 1 <= moves.length <= 10^4
  • moves[i] is -2, -1, or an integer in the range [1, 9].
  • 0 <= pillars.length <= 10^4
  • pillars[i].length == 2
  • -3 * 10^4 <= pillars[i][0], pillars[i][1] <= 3 * 10^4
  • No pillar stands on the charging pad at (0, 0). The same cell may be listed more than once.
  • The value returned is at most 10^10.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def sweep_reach(moves: list[int], pillars: list[list[int]]) -> int:
Java
public long sweepReach(int[] moves, int[][] pillars)

More on the same topics