LeetCode-in-Java

4003. Minimum Cost Path with Alternating Directions III

Hard

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:

The cost of an action is determined as follows:

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).

Example 1:

Input: m = 2, n = 2, penalty = [[5,3],[1,4]]

Output: 8

Explanation:

The optimal path is:

Thus, the total cost is 1 + 2 + 4 + 1 = 8.

Example 2:

Input: m = 2, n = 2, penalty = [[0,7],[3,2]]

Output: 7

Explanation:

The optimal path is:

Thus, the total cost is 1 + 0 + 2 + 0 + 4 = 7.

Example 3:

Input: m = 2, n = 3, penalty = [[8,0,9],[7,4,1]]

Output: 12

Explanation:

The optimal path is:

Thus, the total cost is 1 + 2 + 3 + 0 + 6 = 12.

Constraints:

Solution

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
    public long minCost(int m, int n, int[][] penalty) {
        long inf = Long.MAX_VALUE / 4;
        long[] dist = new long[m * n * 2];
        Arrays.fill(dist, inf);
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        dist[0] = 1;
        pq.add(new long[] {1, 0});
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            int state = (int) top[1];
            if (top[0] > dist[state]) {
                continue;
            }
            int parity = state & 1;
            int cell = state >> 1;
            int i = cell / n;
            int j = cell % n;
            if (i == m - 1 && j == n - 1) {
                return top[0];
            }
            int np = parity ^ 1;
            // wait
            long wait = top[0] + penalty[i][j];
            int ws = (cell << 1) | np;
            if (wait < dist[ws]) {
                dist[ws] = wait;
                pq.add(new long[] {wait, ws});
            }
            for (int d = 0; d < 4; d++) {
                int x = i + dx[d];
                int y = j + dy[d];
                if (x < 0 || y < 0 || x >= m || y >= n) {
                    continue;
                }
                // right/down
                boolean forward = d < 2;
                // parity 0: next action is odd-numbered
                boolean follows = (parity == 0) == forward;
                long c = top[0] + (long) (x + 1) * (y + 1) + (follows ? 0 : penalty[i][j]);
                int ns = ((x * n + y) << 1) | np;
                if (c < dist[ns]) {
                    dist[ns] = c;
                    pq.add(new long[] {c, ns});
                }
            }
        }
        return -1;
    }
}