4003. Minimum Cost Path with Alternating Directions III

You are given two integers m and n representing the number of rows and columns of a grid. Your goal is to reach cell (m - 1, n - 1). You are also given a 2D integer array penalty.

The cost to enter cell (i, j) is (i + 1) * (j + 1).

You begin at cell (0, 0) and initially pay its entrance cost. Actions performed after entering (0, 0) are numbered starting from 1.

On each action, you may move to an adjacent cell or wait in the current cell. A move follows the parity rule if:

• On an odd-numbered action, you move right or down.
• On an even-numbered action, you move left or up.

The cost of an action is determined as follows:

• If you move according to the parity rule, pay only the entrance cost of the destination cell.
• If you move in a direction that violates the parity rule, pay the entrance cost of the destination cell plus penalty[i][j], where (i, j) is the cell you move from.
• If you wait in cell (i, j), pay penalty[i][j].

After every move or wait, the action number increases by 1. Therefore, the required parity alternates after every action, regardless of whether a penalty was paid.

Return the minimum total cost required to reach (m - 1, n - 1).

class Solution {
public:
    long long minCost(int n, int m, vector<vector<int>>& penalty) {
        vector<vector<vector<long long>>> cost(n,vector<vector<long long>>(m, vector<long long>(2, LLONG_MAX)));
        priority_queue<array<long long,4>,vector<array<long long,4>>,greater<array<long long,4>>> q;
        auto push = [&](long long c, long long y, long long x, long long fl) {
            if(cost[y][x][fl] > c) {
                cost[y][x][fl] = c;
                q.push({c,y,x,fl});
            }
        };
        push(1,0,0,0);
        int dy[4]{-1,0,1,0}, dx[4]{0,1,0,-1};
        auto bad = [&](int dir, int fl) {
            if(fl == 0) return dir == 0 or dir == 3;
            return dir == 1 or dir == 2;
        };
        while(q.size()) {
            auto [c,y,x,fl] = q.top(); q.pop();
            if(cost[y][x][fl] != c) continue;
            push(c + penalty[y][x], y, x, !fl);
            for(int i = 0; i < 4; i++) {
                long long ny = y + dy[i], nx = x + dx[i];
                if(0 <= ny and ny < n and 0 <= nx and nx < m) {
                    long long nc = c + (ny + 1) * (nx + 1) + (bad(i,fl) ? penalty[y][x] : 0);
                    push(nc,ny,nx,!fl);
                }
            }
        }
        return min(cost[n-1][m-1][0], cost[n-1][m-1][1]);
    }
};