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 ```python 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** ```text 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** ```text 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** ```text Input: grid = ["R"], query = [1, 1, 1, 2] Output: [] ``` The only robot has distances `[1, 1, 1, 1]`.