Find Robots by Nearest-Blocker Distances

Implement matching_robot_locations(grid: list[list[str]], query: list[int]) -> list[list[int]].

The rectangular grid contains robots "O", empty cells "E", and blockers "X". For every robot, measure the number of moves in each straight direction until reaching either the first blocker cell or the first position outside the grid. Return the robots whose four distances equal query.

Input Domain

• 1 <= len(grid), len(grid[0]) <= 2,000.
• The grid contains at most 1,000,000 cells and all rows have equal length.
• Every cell is exactly "O", "E", or "X".
• query contains four positive integers in [left, top, bottom, right] order.

Output Rules

• A blocker one adjacent move away has distance 1.
• If no "X" occurs first, leaving the grid counts as reaching a blocker boundary. For example, a robot in column 0 has left distance 1.
• Robots and empty cells do not stop the scan.
• Return matching coordinates as [row, column] in ascending row-major order.
• Return an empty list if no robot matches.

Constraints

• Each distance is an exact integer number of moves.
• Target time is O(rows * columns).

Examples

Example 1

Input: grid = [["O","E","E","E","X"],["E","O","X","X","X"],["E","E","E","E","E"],["X","E","O","E","E"],["X","E","X","E","X"]], query = [2,2,4,1]

Output: [[1,1]]

Example 2

Input: grid = [["O","E","O"]], query = [1,1,1,3]

Output: [[0,0]]

Hint: Reuse directional scans

Distances to the previous or next blocker boundary can be propagated across a row or column rather than recomputed from each robot.