以下是 LeetCode 4003. 交替方向的最小路径代价 III 的 JavaScript 实现：

```javascript
/**
 * @param {number} m
 * @param {number} n
 * @param {number[][]} penalty
 * @return {number}
 */
var minCost = function(m, n, penalty) {
    // 最小堆实现（Dijkstra 需要）
    class MinHeap {
        constructor() {
            this.heap = [];
        }
        push(val) {
            this.heap.push(val);
            this._siftUp(this.heap.length - 1);
        }
        pop() {
            if (this.heap.length === 0) return null;
            const top = this.heap[0];
            const end = this.heap.pop();
            if (this.heap.length > 0) {
                this.heap[0] = end;
                this._siftDown(0);
            }
            return top;
        }
        _siftUp(i) {
            const val = this.heap[i];
            while (i > 0) {
                const parent = (i - 1) >> 1;
                if (this.heap[parent][0] <= val[0]) break;
                this.heap[i] = this.heap[parent];
                i = parent;
            }
            this.heap[i] = val;
        }
        _siftDown(i) {
            const val = this.heap[i];
            const len = this.heap.length;
            while (true) {
                let child = (i << 1) + 1;
                if (child >= len) break;
                const right = child + 1;
                if (right < len && this.heap[right][0] < this.heap[child][0]) {
                    child = right;
                }
                if (this.heap[child][0] >= val[0]) break;
                this.heap[i] = this.heap[child];
                i = child;
            }
            this.heap[i] = val;
        }
        get size() {
            return this.heap.length;
        }
    }

    const dirs = [[-1, 0], [0, 1], [0, -1], [1, 0]]; // 上、右、左、下
    const INF = Number.MAX_SAFE_INTEGER;

    // dist[i][j][k]: 到达 (i,j) 且下一步动作奇偶性为 k 的最小成本
    // k=1: 下一步是奇数动作（应向右/下）
    // k=0: 下一步是偶数动作（应向左/上）
    const dist = Array.from({ length: m }, () => 
        Array.from({ length: n }, () => [INF, INF])
    );
    dist[0][0][1] = 1; // 初始在 (0,0)，已付入场费 1，下一步是动作 1（奇数）

    const pq = new MinHeap();
    pq.push([1, 0, 0, 1]); // [cost, i, j, parity]

    while (pq.size > 0) {
        const [d, i, j, k] = pq.pop();

        // 到达终点即是最小成本（Dijkstra 性质）
        if (i === m - 1 && j === n - 1) {
            return d;
        }
        if (d > dist[i][j][k]) continue;

        const p = penalty[i][j];

        // 1. 等待：支付 penalty，奇偶性翻转，位置不变
        const waitCost = d + p;
        if (waitCost < dist[i][j][k ^ 1]) {
            dist[i][j][k ^ 1] = waitCost;
            pq.push([waitCost, i, j, k ^ 1]);
        }

        // 2. 向四个方向移动
        for (let idx = 0; idx < 4; idx++) {
            const x = i + dirs[idx][0];
            const y = j + dirs[idx][1];
            if (x < 0 || x >= m || y < 0 || y >= n) continue;

            // idx: 0=上, 1=右, 2=左, 3=下
            // 奇数动作(k=1)应对应右(1)或下(3) -> idx & 1 === 1
            // 偶数动作(k=0)应对应上(0)或左(2) -> idx & 1 === 0
            const matched = (idx & 1) === k;
            const extra = matched ? 0 : p;

            const moveCost = d + (x + 1) * (y + 1) + extra;
            if (moveCost < dist[x][y][k ^ 1]) {
                dist[x][y][k ^ 1] = moveCost;
                pq.push([moveCost, x, y, k ^ 1]);
            }
        }
    }

    return -1; // 题目保证可达
};
```

核心思路

这道题是带状态的最短路问题，用 Dijkstra 求解：

- 状态设计：`dist[i][j][k]` 表示到达 `(i,j)` 且下一步动作奇偶性为 `k` 的最小成本
  - `k=1`：下一步是奇数动作，应该向右或向下移动
  - `k=0`：下一步是偶数动作，应该向左或向上移动
- 两种动作：
  1. 等待：支付当前格 `penalty`，奇偶性翻转
  2. 移动：向四个方向之一移动。若方向符合当前奇偶性规则，只付目标格入场费 `(x+1)*(y+1)`；否则额外支付当前格 `penalty`。移动后奇偶性翻转
- 由于 JS 没有内置优先队列，代码中附带了一个二叉堆实现的最小堆

复杂度

- 时间：`O(mn · log(mn))`
- 空间：`O(mn)`