Cheapest Grid Trip with Alternating Direction Penalties

# Cheapest Grid Trip with Alternating Direction Penalties You are given an `m`-row, `n`-column grid and a matrix `penalty`. Entering cell `(i, j)` costs `(i + 1) * (j + 1)`. Start at `(0, 0)` and pay its entrance cost, `1`. Number subsequent actions starting at `1`. On each action you may move to a horizontally or vertically adjacent cell within the grid, or wait where you are. The preferred directions alternate: - On an odd-numbered action, moving right or down follows the rule. - On an even-numbered action, moving left or up follows the rule. A move following the rule costs only the destination's entrance cost. A move violating the rule is still allowed, but also costs `penalty[i][j]` for the cell being left. Waiting costs only `penalty[i][j]` at the current cell. Every action advances the action number, so both moves and waits flip the next action's parity, even when a move violates the rule. Return the minimum total cost to reach `(m - 1, n - 1)`. ### Function `long long minCost(int m, int n, vector<vector<int>>& penalty)` ### Example 1 **Input:** `m = 2, n = 2, penalty = [[5, 8], [2, 7]]` **Output:** `9` **Explanation:** Pay `1` at the start. On action `1`, move down to `(1, 0)` for entrance cost `2`. On action `2`, move right to the destination, paying entrance cost `4` plus the departure cell's penalty `2`. The total is `1 + 2 + 4 + 2 = 9`. ### Example 2 **Input:** `m = 1, n = 3, penalty = [[0, 9, 5]]` **Output:** `6` **Explanation:** After the initial cost `1`, wait on action `1` for cost `0`. On action `2`, move right, paying entrance cost `2` and the starting cell's penalty `0`. Action `3` moves right according to the odd-action rule for entrance cost `3`. Total cost is `6`, the sum of the three required entrance costs. ### Constraints - `1 <= m, n <= 100000` - `2 <= m * n <= 100000` - `penalty.length == m`, and every row has length `n`. - `0 <= penalty[i][j] <= 100000` ### Clarifications - There are no blocked cells. All four in-bounds move directions are available on either parity; the parity affects their cost. - A move's extra penalty comes from its departure cell, not its destination. - Waiting does not pay another entrance cost. - The trip ends when the destination is reached; no final wait is required. ### What a Strong Answer Covers - Tracking which parity the next action uses, starting with odd action `1`. - Comparing moves and waits, including zero penalties and rule-violating moves. - Finding the cheapest trip without restricting it to a prescribed geometric path.