Drone Delivery with Battery Swap Stations
Updated
Problem statement
An autonomous delivery drone flies over a city grid. grid[r][c] is 0 for open airspace and 1 for a no-fly building. The drone starts at the depot start = [sr, sc] and must reach the customer at end = [er, ec]. Each move takes the drone one cell up, down, left, or right to an open cell inside the grid.
The battery lasts battery moves, and the drone starts fully charged. Every move uses one unit of charge, so the drone cannot move when its charge is 0.
stations lists the cells that have a battery-swap kiosk. While the drone is on a kiosk cell, it may swap in a fully charged battery, which sets its charge back to battery. Each swap uses one swap voucher, and the whole trip has only vouchers vouchers. Swapping is optional: the drone may fly over a kiosk without swapping, and it may swap at the same kiosk again on a later visit if it still has a voucher.
Return the minimum number of moves needed to fly from start to end. If no delivery is possible, return -1.
Function
minDeliveryMoves(grid: int[][], start: int[], end: int[], battery: int, stations: int[][], vouchers: int) → intExamples
Example 1
grid = [[0,0,0,0],[1,1,0,1],[0,0,0,0]]start = [0,0]end = [2,0]battery = 4stations = [[1,2]]vouchers = 1return = 6The only route is right along the top row to [0,2], down through [1,2], and left along the bottom row to [2,0]. It takes 6 moves, more than one battery.
After 3 moves the drone reaches the kiosk at [1,2] with 1 charge left. It uses its voucher there to swap, so it has 4 charge for the last 3 moves. The answer is 6.
Example 2
grid = [[0,0,0,0],[1,1,0,1],[0,0,0,0]]start = [0,0]end = [2,0]battery = 4stations = [[1,2]]vouchers = 0return = -1This is the same city, but the trip has no vouchers. The only route needs 6 moves and one battery lasts 4, so the delivery is impossible and the answer is -1.
Example 3
grid = [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]start = [0,0]end = [0,4]battery = 3stations = [[1,2],[2,4]]vouchers = 1return = 6The direct route along the top row takes 4 moves, but one battery lasts only 3.
The kiosk at [1,2] is 3 moves from the depot and 3 moves from the customer, so flying there, swapping, and flying on takes 6 moves. The kiosk at [2,4] is 6 moves from the depot, which one battery cannot reach. The answer is 6.
Constraints
1 <= grid.length, grid[i].length <= 50- All rows of
gridhave the same length, and everygrid[i][j]is0or1. startandendare open cells ofgrid.1 <= battery <= 25000 <= stations.length <= 50- Each
stations[k]is a distinct open cell[row, col]ofgrid. 0 <= vouchers <= 50
More Cisco Online Assessment questions
- Auction Sniping Window MinimumOA · Seen Jul 2026
- Collect CoinsOA · Seen Jun 2025
- FizzBuzz ProblemOA · Seen May 2025
- Find Largest Sum Contiguous SubarrayOA · Seen May 2025
- Find Largest Sum of Continuous SequenceOA · Seen May 2025
- Find Palindrome Sub-stringOA · Seen May 2025
- Count Numbers with Digit SumOA · Seen Mar 2025
- Count Numbers with Sum of DigitsOA · Seen Mar 2025
- Maximum Chocolates from Jars (L.C. 198 :)OA · Seen Mar 2025
- Find Elements Largest in Row Smallest in ColumnOA · Seen Mar 2025
Similar questions at other companies
- Safest Shortest Path Through a GridSnowflake · OASnowflake interview questions
- Grid ExplorationIMC Trading · OAIMC Trading interview questions
- Shortest Distance from All BuildingsWaymo · PHONE SCREENWaymo interview questions
- Fire Station Response BillLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Shortest Increasing Path to a TargetUber · ONSITE INTERVIEWUber interview questions
- Minimum Distance to Return a BookGoogle · ONSITE INTERVIEWGoogle interview questions
- Find and Reconstruct a Binary-Matrix PathMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Minimum Cost Path with TeleportationsAmazon · OA
- Competitive ForagingAkuna Capital · OAAkuna Capital interview questions
- Escape the Haunted Castle with TreasuresPersona · OAPersona interview questions