Assign Robots to Nearest Pickup Items on a Grid with Obstacles

A fleet of autonomous delivery robots operates on an `m x n` grid. There are `k` robots and `k` items waiting to be picked up, and each robot must be sent to pick up one item. Each robot should be assigned the item nearest to it; because several robots can be nearest to the same item, conflicts are resolved greedily, matching the closest robot-item pair overall first. The base version of the question uses an open grid; the follow-up adds obstacles. Your function must handle grids with blocked cells, and an open grid is simply a grid with no blocked cells. Return, for each robot, the index of the item assigned to it. ### Function Signature ```python def assign_robots(grid: list[list[int]], robots: list[list[int]], items: list[list[int]]) -> list[int]: ``` `grid[r][c]` is `0` for a free cell and `1` for a blocked cell. `robots[i] = [r, c]` and `items[j] = [r, c]` give the row and column of robot `i` and item `j`. ### Rules - A robot moves one cell per step, up, down, left or right. It never leaves the grid and never enters a blocked cell. The distance between robot `i` and item `j` is the minimum number of steps from the robot's cell to the item's cell. On a grid with no blocked cells this equals `abs(r1 - r2) + abs(c1 - c2)`. - Assignment proceeds in rounds. In each round, consider every pair of a still-unassigned robot `i` and a still-unassigned item `j`, and pick the pair with the smallest distance. If several pairs tie, pick the one with the smallest robot index `i`; if they still tie, the one with the smallest item index `j`. Assign item `j` to robot `i` and remove both from further rounds. - Rounds continue until every robot has an item. Because there are as many items as robots, every robot receives exactly one item and every item is assigned exactly once. - Return a list `result` of length `k` where `result[i]` is the index of the item assigned to robot `i`. ### Constraints - `1 <= m, n <= 50`, where `m = len(grid)` and `n = len(grid[0])`; every row has length `n`. - Each `grid[r][c]` is `0` or `1`. - `1 <= k <= 50` and `len(robots) == len(items) == k`. - Every position satisfies `0 <= r < m` and `0 <= c < n`, and every robot and every item stands on a free cell. - Robot positions are pairwise distinct, and item positions are pairwise distinct. A robot and an item may share a cell, in which case their distance is `0`. - Every item is reachable from every robot, so every distance is defined and is less than `m * n`, which is at most 2,500. ### Examples **Example 1** ```text Input: grid = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] robots = [[0, 0], [0, 3]] items = [[0, 2], [2, 0]] Output: [1, 0] ``` Robot 0 is 2 steps from both items. Robot 1 is 1 step from item 0 and 5 steps from item 1. The closest pair overall is robot 1 with item 0, so it is matched first, and robot 0 receives the remaining item 1. **Example 2** ```text Input: grid = [[0, 0, 0], [0, 0, 0], [0, 0, 0]] robots = [[0, 1], [2, 1]] items = [[1, 1], [1, 0]] Output: [0, 1] ``` Both robots are 1 step from item 0 and 2 steps from item 1. The two pairs at distance 1 tie, so the smaller robot index wins: robot 0 receives item 0, and robot 1 receives item 1. **Example 3** ```text Input: grid = [[0, 0, 0], [1, 1, 0], [0, 0, 0]] robots = [[0, 0], [2, 2]] items = [[2, 0], [0, 2]] Output: [1, 0] ``` The blocked cells in row 1 force robot 0 around through column 2, so it is 6 steps from item 0 and 2 steps from item 1. Robot 1 is 2 steps from each item. Three pairs tie at distance 2; the smallest robot index among them is 0, whose only pair at that distance is with item 1, so robot 0 receives item 1 and robot 1 receives item 0. If the blocked cells were ignored, all four distances would be 2 and the answer would be `[0, 1]`.