Welcome to Subscribe On Youtube

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

The path will always begin by entering cell (0, 0) on move 1 and paying the entrance cost.

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

  • 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;
    }
}

  • 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;
    }
};

  • 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


  • 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
}

  • 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;
}

All Problems

All Solutions