Minimum Cost Path in Grid with Fuel, Blocked Cells, and Recharge Cells

You are given an m x n grid and need to move from (0,0) to (m-1,n-1). You are given: grid_cost[i][j]: cost to enter cell (i,j). The starting cell (0,0) cost is included. blocked[i][j]: if True, the cell is not enterable. recharge[i][j]: if True, stepping onto this cell refills your fuel to K. You have fuel (or jumps) with maximum capacity K. Each move to an adjacent cell consumes 1 fuel (clarify movement/consumption rules in interview). Fuel is allowed to be 0 when you reach the destination. Return the minimum total cost to reach (m-1,n-1), or -1 if unreachable. Follow-up If K is very large, O(m*n*K) state-space search may be too big. How would you optimize? Example Input 2 2 2 1 1 1 1 0 0 0 0 0 0 0 0 1 Output 3