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:
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:
(0, 0).(0, 0) is (0 + 1) * (0 + 1) = 1.Example 2:
Input: m = 2, n = 1
Output: 3
Explanation:
(0, 0) with cost (0 + 1) * (0 + 1) = 1.(1, 0) with cost (1 + 1) * (0 + 1) = 2.1 + 2 = 3.
Constraints:
1 <= m, n <= 106Due to the movement rules given in the problem, in fact, only the following three cases can reach the target cell:
1 times 1 grid, with a cost of 1.2 rows and 1 column, with a cost of 3.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).
Java
C++
Go
TypeScript
Practice Minimum Cost Path with Alternating Directions I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor