Skip to content

3596. Minimum Cost Path with Alternating Directions I πŸ”’

Description

You are given two integers m and n representing the number of rows and columns of a grid, respectively.

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

You start at cell (0, 0) on move 1.

At each step, you move to an adjacent cell, following an alternating pattern:

  • On odd-numbered moves, you must move either right or down.
  • On even-numbered moves, you must move either left or up.

Return the minimum total cost required to reach (m - 1, n - 1). If it is impossible, return -1.

 

Example 1:

Input: m = 1, n = 1

Output: 1

Explanation:

  • You start at cell (0, 0).
  • The cost to enter (0, 0) is (0 + 1) * (0 + 1) = 1.
  • Since you're at the destination, the total cost is 1.

Example 2:

Input: m = 2, n = 1

Output: 3

Explanation:

  • You start at cell (0, 0) with cost (0 + 1) * (0 + 1) = 1.
  • Move 1 (odd): You can move down to (1, 0) with cost (1 + 1) * (0 + 1) = 2.
  • Thus, the total cost is 1 + 2 = 3.

 

Constraints:

  • 1 <= m, n <= 106

Solutions

Solution 1: Brain Teaser

Due to the movement rules given in the problem, in fact, only the following three cases can reach the target cell:

  1. A \(1 \times 1\) grid, with a cost of \(1\).
  2. A grid with \(2\) rows and \(1\) column, with a cost of \(3\).
  3. A grid with \(1\) row and \(2\) columns, with a cost of \(3\).

For all other cases, it is impossible to reach the target cell, so return \(-1\).

The time complexity is \(O(1)\), and the space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def minCost(self, m: int, n: int) -> int:
        if m == 1 and n == 1:
            return 1
        if m == 2 and n == 1:
            return 3
        if m == 1 and n == 2:
            return 3
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int minCost(int m, int n) {
        if (m == 1 && n == 1) {
            return 1;
        }
        if (m == 1 && n == 2) {
            return 3;
        }
        if (m == 2 && n == 1) {
            return 3;
        }
        return -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int minCost(int m, int n) {
        if (m == 1 && n == 1) {
            return 1;
        }
        if (m == 1 && n == 2) {
            return 3;
        }
        if (m == 2 && n == 1) {
            return 3;
        }
        return -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func minCost(m int, n int) int {
    if m == 1 && n == 1 {
        return 1
    }
    if m == 1 && n == 2 {
        return 3
    }
    if m == 2 && n == 1 {
        return 3
    }
    return -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function minCost(m: number, n: number): number {
    if (m === 1 && n === 1) {
        return 1;
    }
    if (m === 1 && n === 2) {
        return 3;
    }
    if (m === 2 && n === 1) {
        return 3;
    }
    return -1;
}

Comments