Cheapest Grid Path with a Turn Limit

# Cheapest Grid Path with a Turn Limit You are given a rectangular matrix `grid` and an integer `k`. The value in a cell is the cost of visiting it. Start at the top-left cell `(0, 0)` and reach the bottom-right cell. Each move goes one cell up, down, left or right, staying inside the grid. The path costs the sum of all visited cell values, including the start and destination. Revisiting a cell charges its value again. A turn occurs whenever the direction changes between consecutive moves. The first move does not count as a turn. Continuing in the same direction does not add a turn, while changing to any other direction does. Return the minimum path cost using at most `k` turns, or `-1` if no such path exists. ### Function `int minCost(vector<vector<int>>& grid, int k)` ### Example 1 **Input:** `grid = [[1, 9, 1], [1, 1, 1], [9, 9, 1]], k = 2` **Output:** `5` **Explanation:** Follow `(0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> (2, 2)`. The directions are down, right, right, down, giving two turns. All five visited cells cost `1`. Any path needs at least four moves, and every cell costs at least `1`, so `5` is minimal. ### Example 2 **Input:** `grid = [[4, 0, 3, 2]], k = 0` **Output:** `9` **Explanation:** Move right three times. No direction changes are needed, and the total cost, including both endpoints, is `4 + 0 + 3 + 2 = 9`. ### Constraints - `1 <= grid.length <= 75` - Every row has the same length `n`, with `1 <= n <= 75`. - `0 <= grid[i][j] <= 1000` - `0 <= k < min(grid.length, n)` ### Clarifications - All four directions are allowed; a path is not required to move only right and down. - Reversing direction counts as one turn, just like any other direction change. - Using fewer than `k` turns is allowed. - If the grid has only one cell, no moves are needed and its value is the path cost. ### What a Strong Answer Covers - Charging every visit while tracking the direction changes of the actual move sequence. - Handling a free choice of first-move direction and paths using fewer than the turn limit. - Distinguishing unreachable turn budgets from valid paths, including zero-cost cells and one-dimensional grids.