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

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

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

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

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].