Find Robots by Blocker Distances
Learn this problem
UberFULLTIMEPHONE SCREENProblem statement
Given a non-empty rectangular grid grid and a four-element array query, return the coordinates of every robot whose nearest-blocker distances match query.
Each grid cell is one of:
O: a robot.E: an empty cell.X: a blocker.
The query order is [left, top, bottom, right]. In one direction, the distance is the number of steps from the robot to the first X cell. If there is no blocker before the grid edge, use the number of steps to the first out-of-bounds position. The blocker or out-of-bounds step is included in the distance.
Return zero-based [row, column] pairs in row-major order.
Function
findRobots(grid: String[], query: int[]) → int[][]Examples
Example 1
grid = ["OEEEX","EOXXX","EEEEE","XEOEE","XEXEX"]query = [2,2,4,1]return = [[1,1]]The robot at [1,1] is two steps from the left boundary, two steps from the top boundary, four steps from the bottom boundary, and one step from the blocker on its right.
Example 2
grid = ["O"]query = [1,1,1,1]return = [[0,0]]Every direction reaches the first out-of-bounds position in one step.
Example 3
grid = ["XOXOX","XXXXX","XOXOX"]query = [1,1,1,1]return = [[0,1],[0,3],[2,1],[2,3]]Each robot is immediately surrounded by blockers or a grid boundary, so all four coordinates match and are returned in row-major order.
Constraints
1 <= grid.length <= 200.1 <= grid[i].length <= 200.- Every row has the same length.
- Every cell is exactly
O,E, orX. query.length == 4.- Every query distance is positive and at most
max(grid.length, grid[0].length) + 1.