You are given an m x n grid where each cell represents a location. The grid contains different types of cells:

• '.' represents an empty, traversable cell.
• '#' represents a rock or an obstacle that you cannot pass through.
• 'S' is your starting position (there is exactly one).
• 'D' is your destination (there is exactly one).
• 'G' is a gas station, which is traversable (there can be multiple or none).

You are also given an integer fuelCapacity. You start at 'S' with a full tank of fuel, equal to fuelCapacity.

Your movement is restricted to the four cardinal directions (up, down, left, right). Each move to an adjacent cell costs 1 unit of fuel. You cannot make a move if your fuel level drops below zero.

When you enter a cell with a gas station G, your fuel is instantly and fully refilled to fuelCapacity. This refueling action is part of the move onto the gas station cell and has no extra step cost.

Your goal is to find the minimum number of steps to travel from 'S' to 'D'. Return -1 If it's impossible to reach the destination.

Example 1:

Input: grid = [["S", ".", ".", "#", "."],         [".", "#", ".", "G", "."],         [".", "#", ".", ".", "."],         [".", ".", "#", ".", "D"]], fuelCapacity = 4 Output: 7 Explanation: One of the shortest paths involves traveling to the gas station at (1, 3) to refuel before proceeding to the destination. The total steps taken are 7.

Example 2:

Input: grid = [["S", ".", "#", "G"],         [".", ".", "#", "."],         [".", "G", ".", "."],         ["#", "#", ".", "D"]], fuelCapacity = 3 Output: 6

Example 3:

Input: grid = [["S",".",".","D"]], fuelCapacity = 2 Output: -1