Find Robots by Nearest-Blocker Distances

Problem Statement

You are given an m x n grid representing an autonomous warehouse floor. Each cell in the grid contains one of the following characters:

• 'R': A robot
• 'X': A blocker (obstacle)
• '.': An empty cell

For any robot located at cell (r, c), its distance to an obstacle or boundary in a given direction is defined as the number of steps required to reach the obstacle or step just outside the grid boundary:

• Left distance: c - c_blocker if there is a blocker at (r, c_blocker) with c_blocker < c and no other blockers between them. If no blocker exists to the left, it is c + 1 (the distance to step off the left edge).
• Top distance: r - r_blocker if there is a blocker at (r_blocker, c) with r_blocker r and no other blockers between them. If no blocker exists below, it is m - r.
• Right distance: c_blocker - c if there is a blocker at (r, c_blocker) with c_blocker > c and no other blockers between them. If no blocker exists to the right, it is n - c.

Robots do not block other robots. You are given a target query as a 4-element list of integers: [left, top, bottom, right].

Write a function that finds all robots whose four directional distances match the query exactly. Return their coordinates [r, c] sorted in lexicographical order.

Function Signature

def find_robots(
    grid: list[list[str]], 
    query: list[int]
) -> list[list[int]]:
    pass

Examples

Example 1

Input:

grid = [
    [".", "R", ".", "X"],
    ["X", ".", ".", "."],
    [".", "R", ".", "."]
]
query = [2, 1, 3, 2]

Output:

[[0, 1]]

Explanation:

• For robot at (0, 1):
  • Left: No blockers to the left, distance to left edge is 1 + 1 = 2.
  • Top: No blockers above, distance to top edge is 0 + 1 = 1.
  • Bottom: No blockers below in column 1, distance to bottom edge is 3 - 0 = 3.
  • Right: Nearest blocker is at (0, 3), distance is 3 - 1 = 2.
  • Signature: [2, 1, 3, 2], which matches the query.
• For robot at (2, 1):
  • Left: 2, Top: 3, Bottom: 1, Right: 3. Signature: [2, 3, 1, 3], no match.

Example 2

Input:

grid = [
    ["R", ".", "R"],
    [".", "X", "."],
    ["R", ".", "R"]
]
query = [1, 1, 3, 3]

Output:

[[0, 0]]

Explanation:

• Robot at (0, 0): Left is 1, Top is 1, Bottom is 3, Right is 3. Matches [1, 1, 3, 3].

Constraints

• m == len(grid)
• n == len(grid[0])
• 1 = 1
• Each grid[r][c] is 'R', 'X', or '.'. There is at least one 'R' in grid.