Find robots in a grid whose four-direction distances to blockers match a query

A rectangular grid contains robots, blockers and empty cells. For each robot, measure how far it is from the nearest blocker in each of the four directions (up, down, left and right), where the edge of the grid also counts as a blocker. Given the four distances you are looking for, return the positions of all robots whose distances match exactly.

Function Signature

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

grid[i][j] is 'R' for a robot, '#' for a blocker and '.' for an empty cell. query is [up, down, left, right].

Rules

• Row 0 is the top row and column 0 is the leftmost column. The grid has m rows and n columns.
• Only '#' cells block. Robots and empty cells never block, so a robot's distance is measured past any other robots in the way.
• For a robot at (r, c):
• up = r - i, where i is the largest row index with i < r and grid[i][c] == '#', or i = -1 if there is none.
• down = i - r, where i is the smallest row index with i > r and grid[i][c] == '#', or i = m if there is none.
• left = c - j, where j is the largest column index with j < c and grid[r][j] == '#', or j = -1 if there is none.
• right = j - c, where j is the smallest column index with j > c and grid[r][j] == '#', or j = n if there is none.
• A robot directly next to a blocker or to the edge therefore has distance 1 in that direction, and every distance is at least 1.
• A robot matches when its [up, down, left, right] equals query element by element.
• Return [row, col] for every matching robot, sorted by row and then by column. Return an empty list if no robot matches.

Constraints

• 1 <= m <= 500 and 1 <= n <= 500, where m = len(grid) and n = len(grid[0]); all rows have the same length.
• Every character of grid is 'R', '#' or '.'. The grid may contain no robots, and every cell may be a robot.
• len(query) == 4 and 1 <= query[k] <= 10^9 for every k.

Examples

Example 1

Input: grid = ["R.#.R", ".R...", "#.R.R"], query = [2, 2, 2, 4]
Output: [[1, 1]]

The robots' distances [up, down, left, right] are: (0, 0) has [1, 2, 1, 2], (0, 4) has [1, 3, 2, 1], (1, 1) has [2, 2, 2, 4], (2, 2) has [2, 1, 2, 3] and (2, 4) has [3, 1, 4, 1]. Robot (1, 1) has no blocker in any direction, so all four distances are measured to the edges: up = 1 - (-1) = 2, down = 3 - 1 = 2, left = 1 - (-1) = 2 and right = 5 - 1 = 4.

Example 2

Input: grid = ["R#R.", "....", "R#R#"], query = [3, 1, 1, 1]
Output: [[2, 0], [2, 2]]

Both robots in the bottom row have [3, 1, 1, 1]: the robots above them in row 0 do not block, so up is measured to the top edge, and on the other three sides each is next to a blocker or the edge. The robots in row 0 have up = 1, so they do not match.

Example 3

Input: grid = ["R"], query = [1, 1, 1, 2]
Output: []

The only robot has distances [1, 1, 1, 1].