Minimum cost path with alternating directions i

Math Brainteaser

70.2% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(1)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(m: i32, n: i32) -> i32 {
    // Odd moves: right or down. Even moves: left or up.
    // From (0,0), move 1 goes to (0,1) or (1,0).
    // From those edge cells, even move forces return to (0,0).
    // For any m>=2,n>=2 the target (m-1,n-1) is unreachable
    // because backward-tracing always hits OOB or loops.
    if m == 1 && n == 1 {
      1
    } else if m + n == 3 {
      3
    } else {
      -1
    }
  }
}