Shortest Path on a Grid with Gas Stations (State Reset)

You are given an m x n grid grid where: S is the start T is the target # is a wall (blocked) . is an empty cell G is a gas station You start at S. You may move one cell at a time in 4 directions (up/down/left/right), staying within bounds and not entering #. You have a fuel/range capacity K, meaning you can take at most K consecutive steps without refueling. Each move costs 1 unit of fuel. If you need to take the (K+1)-th step since the last refuel, the move is only possible if you are at a gas station. Whenever you enter/reach a gas station cell G, your fuel is instantly refilled back to K (i.e., the fuel state is reset). You may refuel any number of times. Return the minimum number of steps needed to reach T from S, or -1 if impossible. Input (stdin) Line 1: m n K Next m lines: strings of length n describing the grid Output (stdout) One integer: the minimum steps, or -1 Constraints 1 <= m,n <= 200 0 <= K <= 10^3 Exactly one S and one T exist Example Input: 3 4 3 S..# .G.. ...T Output: 5 Example Input 3 4 3 S..# .G.. ...T Output 5