Fuel-Limited Grid Route
MediumGraphs ยท Bloomberg
Given grid, a list of equal-length strings, return the fewest moves a vehicle needs to get from S to G, or -1 if it cannot.
The cells are . open, # blocked, F charging station, S start and G goal. The vehicle can enter any cell except #. Each move goes to an adjacent cell (up, down, left or right) and uses 1 unit of fuel, so it cannot move with an empty tank. It starts with fuel units, and every time it enters an F cell the tank is filled to capacity.
Example 1
- Input:
- grid = ["S..#G", ".#.#.", ".F..."], fuel = 3, capacity = 5
- Output:
- 8
- Explanation
- The top route is blocked. The vehicle reaches
Fin 3 moves with an empty tank, refills to 5, and spends all 5 reachingG.
Example 2
- Input:
- grid = ["S...G", ".###.", "F...."], fuel = 3, capacity = 6
- Output:
- 8
- Explanation
- The 4-move direct route needs 4 units, so the vehicle detours through
Ffirst.
Example 3
- Input:
- grid = ["S..#G", ".#.#.", ".F..."], fuel = 3, capacity = 4
- Output:
- -1
Constraints
1 <= grid.length <= 30and1 <= grid[i].length <= 30gridcontains exactly oneSand oneG; every other character is.,#orF0 <= fuel <= capacity <= 100