Multi-Source BFS with Obstacles and Variable Weights

Mid February, 2026

Amazon

Mid-level

Problem (Warehouse Dispatch Readiness) You are given an m x n grid representing a warehouse yard. Each cell can contain 0 (no truck present), 1 (a truck that is ready to be dispatched), or -1 (an obstacle that blocks movement). Dispatch operations start simultaneously from all boundary cells that contain trucks (1), since those trucks can directly exit the warehouse and initiate dispatch for others. Every minute, a dispatched truck enables its adjacent trucks (up, down, left, right only) to dispatch as well, provided there is no obstacle in between. The task is to compute the minimum time required to dispatch all trucks in the grid. If some trucks can never be reached because they are blocked by obstacles, return -1. Follow-up (Variable Dispatch Time) Now assume each truck takes a different amount of time to prepare for dispatch. Instead of every propagation taking 1 minute, each cell has an associated dispatch delay, and the time to dispatch spreads based on that delay. The goal becomes finding the minimum total time required for all trucks to be dispatched considering these non-uniform times, which changes the problem from a level-by-level spread to a shortest-time propagation problem (multi-source weighted traversal).