跳转至

3596. 交替方向的最小路径代价 I 🔒

题目描述

给定两个整数 m 和 n 分别表示一个网格的行数和列数。

进入单元格 (i, j) 的花费定义为 (i + 1) * (j + 1)。

路径始终从第 1 步进入单元格 (0, 0) 并支付入场花费开始。

在每一步，你移动到 相邻 的单元格，遵循交替的模式：

  • 在 奇数次 移动，你必须向 右方 或 下方 移动。
  • 在 偶数次 移动，你必须向 左方 或 上方 移动。

返回到达 (m - 1, n - 1) 的最小总花费。如果不可能到达，返回 -1。

 

示例 1：

输入：m = 1, n = 1

输出：1

解释：

  • 你从单元格 (0, 0) 开始。
  • 进入 (0, 0) 的花费是 (0 + 1) * (0 + 1) = 1。
  • 由于你已经到达了目标，总花费为 1。

示例 2：

输入：m = 2, n = 1

输出：3

解释：

  • 你从单元格 (0, 0) 开始，花费为 (0 + 1) * (0 + 1) = 1。
  • 第 1 次移动（奇数次）：你可以向下移动到 (1, 0)，花费为 (1 + 1) * (0 + 1) = 2。
  • 因此，总花费是 1 + 2 = 3。

 

提示：

  • 1 <= m, n <= 106

解法

方法一：脑筋急转弯

由于题目中给定的移动规则，实际上只有以下三种情况可以到达目标单元格：

  1. 行列数为 \(1 \times 1\) 的网格，花费为 \(1\)。
  2. 行数为 \(2\)，列数为 \(1\) 的网格，花费为 \(3\)。
  3. 行数为 \(1\)，列数为 \(2\) 的网格，花费为 \(3\)。

对于其他情况，无法到达目标单元格，返回 \(-1\)。

时间复杂度 \(O(1)\)，空间复杂度 \(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;
}

评论