4003 LeetCode problem solution

Previously, I described the first problems from 4000 to 4010, except for 4004 and 4005.

Below is the solution to LeetCode problem 4003.


LeetCode link: 4003. Minimum Cost Path with Alternating Directions III


4003 LeetCode problem: description

Hard level problem.


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


Example 1:


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

Explanation:

Start at (0, 0) and pay 1.
On action 1, move down to (1, 0) and pay 2.
On action 2, move right to (1, 1). Right violates the even-action direction rule, so pay the entrance cost 4 and penalty[1][0] = 1.
Total 1 + 2 + 4 + 1 = 8.


Example 2:


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

Explanation:

Wait at (0, 0) on action 1 and pay 0. Then move right on action 2; the direction violates the parity rule, but penalty[0][0] = 0. Finally, move down on action 3.

Total 1 + 0 + 2 + 0 + 4 = 7.


Example 3:


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

Explanation:

Use the path (0, 0) -> (0, 1) -> (0, 2) -> (1, 2).
The move from (0, 1) to (0, 2) violates the even-action rule, but penalty[0][1] = 0.
Total 1 + 2 + 3 + 0 + 6 = 12.


Constraints:

  • 1 <= m, n <= 10⁵
  • 2 <= m * n <= 10⁵
  • penalty.length == m
  • penalty[i].length == n
  • 0 <= penalty[i][j] <= 10⁵

LeetCode 4003 problem: solution explanation

We can solve this problem using Dijkstra's Algorithm + Parity State.

The cost of the next move depends on both the current cell and the parity of the next action. Therefore, each cell has two states:

(i, j, odd)
(i, j, even)

All transition costs are non-negative, so Dijkstra finds the minimum-cost path between these states.


Step 1: Define the state

Let:

dist[i][j][parity]

store the minimum cost to reach (i, j) when the next action has the given parity.

We use:

parity = 1 -> odd
parity = 0 -> even

The entrance cost of (0, 0) is:

1

so the initial state is:

dist[0][0][1] = 1

Step 2: Process moves

From each cell, we can move up, right, left, or down.

The entrance cost of destination (x, y) is:

(x + 1) * (y + 1)

On an odd action, right and down follow the direction rule.

On an even action, left and up follow the direction rule.

If the move violates the rule, add:

penalty[i][j]

After every move, flip the parity:

parity ^ 1

Step 3: Process waiting

We can stay in the current cell and pay:

penalty[i][j]

The cell does not change, but the action number does, so the parity flips:

(i, j, parity) -> (i, j, parity ^ 1)

Step 4: Example

For:

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

start at:

(0, 0, odd)
cost = 1

Move down on the odd action:

(0, 0, odd) -> (1, 0, even)

Down follows the rule:

cost = 1 + 2 = 3

Now move right to (1, 1).

Right violates the even-action rule, so add the destination entrance cost and the penalty of (1, 0):

4 + 1 = 5

The total cost is:

3 + 5 = 8

Dijkstra checks all cheaper reachable states first, so when the destination is removed from the priority queue, its cost is minimal.


LeetCode 4003 problem: complexity

There are two parity states for every grid cell:

2 * m * n

Each state has at most five transitions: four moves and one wait.


Time complexity: O(m * n * log(m * n))
Space complexity: O(m * n)


Pattern: Shortest Path / State Graph
Technique: Dijkstra, Priority Queue, Parity State, Grid Graph


LeetCode 4003 C++ solution

class Solution {
public:
  long long minCost(int m, int n, vector<vector<int>>& penalty)
  {
    auto qavirelmon = make_tuple(m, n, penalty);

    const long long INF = LLONG_MAX;

    vector<vector<array<long long, 2>>> dist(m, vector<array<long long, 2>>(n, {INF, INF}));

    priority_queue<array<long long, 4>, vector<array<long long, 4>>, greater<array<long long, 4>>> pq;

    dist[0][0][1] = 1;
    pq.push({1, 0, 0, 1});

    int dirs[4][2] = {
      {-1, 0},
      {0, 1},
      {0, -1},
      {1, 0}
    };

    while(!pq.empty())
    {
      auto [cost, i, j, parity] = pq.top();
      pq.pop();

      if(cost != dist[i][j][parity]) continue;

      if(i == m - 1 && j == n - 1) return cost;

      long long waitCost = cost + penalty[i][j];

      if(waitCost < dist[i][j][parity ^ 1])
      {
        dist[i][j][parity ^ 1] = waitCost;
        pq.push({waitCost, i, j, parity ^ 1});
      }

      for(int d = 0; d < 4; d++)
      {
        int x = i + dirs[d][0];
        int y = j + dirs[d][1];

        if(x < 0 || x >= m || y < 0 || y >= n) continue;

        bool followsRule = (parity == 1 && (d == 1 || d == 3)) || (parity == 0 && (d == 0 || d == 2));

        long long nextCost = cost + 1LL * (x + 1) * (y + 1);

        if(!followsRule) nextCost += penalty[i][j];

        if(nextCost < dist[x][y][parity ^ 1])
        {
          dist[x][y][parity ^ 1] = nextCost;
          pq.push({nextCost, x, y, parity ^ 1});
        }
      }
    }

    return -1;
  }
};

LeetCode 4003 Java solution

class Solution {
  public long minCost(int m, int n, int[][] penalty) {
    Object[] qavirelmon = {m, n, penalty};

    long INF = Long.MAX_VALUE;

    long[][][] dist = new long[m][n][2];

    for(int i = 0; i < m; i++)
      for(int j = 0; j < n; j++)
        Arrays.fill(dist[i][j], INF);

    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));

    dist[0][0][1] = 1;
    pq.offer(new long[]{1, 0, 0, 1});

    int[][] dirs = {
      {-1, 0},
      {0, 1},
      {0, -1},
      {1, 0}
    };

    while(!pq.isEmpty()) {
      long[] current = pq.poll();

      long cost = current[0];
      int i = (int)current[1];
      int j = (int)current[2];
      int parity = (int)current[3];

      if(cost != dist[i][j][parity]) continue;

      if(i == m - 1 && j == n - 1) return cost;

      long waitCost = cost + penalty[i][j];

      if(waitCost < dist[i][j][parity ^ 1]) {
        dist[i][j][parity ^ 1] = waitCost;
        pq.offer(new long[]{waitCost, i, j, parity ^ 1});
      }

      for(int d = 0; d < 4; d++) {
        int x = i + dirs[d][0];
        int y = j + dirs[d][1];

        if(x < 0 || x >= m || y < 0 || y >= n) continue;

        boolean followsRule = (parity == 1 && (d == 1 || d == 3)) || (parity == 0 && (d == 0 || d == 2));

        long nextCost = cost + (long)(x + 1) * (y + 1);

        if(!followsRule) nextCost += penalty[i][j];

        if(nextCost < dist[x][y][parity ^ 1]) {
          dist[x][y][parity ^ 1] = nextCost;
          pq.offer(new long[]{nextCost, x, y, parity ^ 1});
        }
      }
    }

    return -1;
  }
}

LeetCode 4003 JavaScript solution

var minCost = function(m, n, penalty) {
  const qavirelmon = [m, n, penalty];

  const dist = Array.from({length: m}, () => Array.from({length: n}, () => [Infinity, Infinity]));

  const pq = new MinPriorityQueue(x => x[0]);

  dist[0][0][1] = 1;
  pq.enqueue([1, 0, 0, 1]);

  const dirs = [
    [-1, 0],
    [0, 1],
    [0, -1],
    [1, 0]
  ];

  while(!pq.isEmpty()) {
    const [cost, i, j, parity] = pq.dequeue();

    if(cost !== dist[i][j][parity]) continue;

    if(i === m - 1 && j === n - 1) return cost;

    const waitCost = cost + penalty[i][j];

    if(waitCost < dist[i][j][parity ^ 1]) {
      dist[i][j][parity ^ 1] = waitCost;
      pq.enqueue([waitCost, i, j, parity ^ 1]);
    }

    for(let d = 0; d < 4; d++) {
      const x = i + dirs[d][0];
      const y = j + dirs[d][1];

      if(x < 0 || x >= m || y < 0 || y >= n) continue;

      const followsRule = (parity === 1 && (d === 1 || d === 3)) || (parity === 0 && (d === 0 || d === 2));

      let nextCost = cost + (x + 1) * (y + 1);

      if(!followsRule) nextCost += penalty[i][j];

      if(nextCost < dist[x][y][parity ^ 1]) {
        dist[x][y][parity ^ 1] = nextCost;
        pq.enqueue([nextCost, x, y, parity ^ 1]);
      }
    }
  }

  return -1;
};

LeetCode 4003 TypeScript solution

function minCost(m: number, n: number, penalty: number[][]): number {
  const qavirelmon = [m, n, penalty];

  const dist: number[][][] = Array.from(
    {length: m},
    () => Array.from({length: n}, () => [Infinity, Infinity])
  );

  const pq = new MinPriorityQueue<number[]>(x => x[0]);

  dist[0][0][1] = 1;
  pq.enqueue([1, 0, 0, 1]);

  const dirs: number[][] = [
    [-1, 0],
    [0, 1],
    [0, -1],
    [1, 0]
  ];

  while(!pq.isEmpty()) {
    const [cost, i, j, parity] = pq.dequeue();

    if(cost !== dist[i][j][parity]) continue;

    if(i === m - 1 && j === n - 1) return cost;

    const waitCost = cost + penalty[i][j];

    if(waitCost < dist[i][j][parity ^ 1]) {
      dist[i][j][parity ^ 1] = waitCost;
      pq.enqueue([waitCost, i, j, parity ^ 1]);
    }

    for(let d = 0; d < 4; d++) {
      const x = i + dirs[d][0];
      const y = j + dirs[d][1];

      if(x < 0 || x >= m || y < 0 || y >= n) continue;

      const followsRule =
        (parity === 1 && (d === 1 || d === 3)) ||
        (parity === 0 && (d === 0 || d === 2));

      let nextCost = cost + (x + 1) * (y + 1);

      if(!followsRule) nextCost += penalty[i][j];

      if(nextCost < dist[x][y][parity ^ 1]) {
        dist[x][y][parity ^ 1] = nextCost;
        pq.enqueue([nextCost, x, y, parity ^ 1]);
      }
    }
  }

  return -1;
}

LeetCode 4003 Python solution

class Solution:
  def minCost(self, m: int, n: int, penalty: List[List[int]]) -> int:
    qavirelmon = (m, n, penalty)

    dist = [
      [[float('inf'), float('inf')] for _ in range(n)]
      for _ in range(m)
    ]

    dist[0][0][1] = 1

    heap = [(1, 0, 0, 1)]

    dirs = [
      (-1, 0),
      (0, 1),
      (0, -1),
      (1, 0)
    ]

    while heap:
      cost, i, j, parity = heappop(heap)

      if cost != dist[i][j][parity]: continue

      if i == m - 1 and j == n - 1: return cost

      wait_cost = cost + penalty[i][j]

      if wait_cost < dist[i][j][parity ^ 1]:
        dist[i][j][parity ^ 1] = wait_cost
        heappush(heap, (wait_cost, i, j, parity ^ 1))

      for d, (dx, dy) in enumerate(dirs):
        x = i + dx
        y = j + dy

        if x < 0 or x >= m or y < 0 or y >= n: continue

        follows_rule = (
          (parity == 1 and (d == 1 or d == 3)) or
          (parity == 0 and (d == 0 or d == 2))
        )

        next_cost = cost + (x + 1) * (y + 1)

        if not follows_rule: next_cost += penalty[i][j]

        if next_cost < dist[x][y][parity ^ 1]:
          dist[x][y][parity ^ 1] = next_cost
          heappush(heap, (next_cost, x, y, parity ^ 1))

    return -1