Simulate robot on grid with obstacles
Overview
This question evaluates proficiency in simulating stateful movement on a grid, efficient use of data structures for obstacle detection, and analysis of time and space complexity under large input constraints.
A robot starts at (0, 0) on an unbounded integer grid. You are given a sequence of commands consisting of characters U, D, L, and R, and a set of blocked cells (obstacles). For each command, the robot attempts to move one cell in the indicated direction; if the destination cell is blocked, it does not move for that command and proceeds to the next. Return the maximum squared Euclidean distance from the origin reached at any time during the simulation. Design an algorithm that handles up to 1e5 commands and 1e5 obstacles efficiently; describe data structures (e.g., hash set for obstacles), complexity, and edge cases.