Minimum Cost Path with Alternating Directions I

Minimum Cost Path with Alternating Directions I - Problem

Math Brainteaser Medium

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.

Input & Output

Example 1 — Small 2x2 Grid

$ Input: m = 2, n = 2

› Output: 10

💡 Note: Start at (0,0) cost=1. Path: (0,0)→(0,1)→(0,0)→(1,0)→(1,1). Costs: 1+2+1+2+4=10

Example 2 — Simple 1x2 Grid

$ Input: m = 1, n = 2

› Output: 3

💡 Note: Start at (0,0) cost=1, move right to (0,1) cost=2. Total: 1+2=3

Example 3 — Impossible Case

$ Input: m = 3, n = 3

› Output: -1

💡 Note: With alternating movement rules, reaching (2,2) becomes impossible from (0,0)

Constraints

1 ≤ m, n ≤ 10³
Grid cells have cost (i+1) * (j+1)

Visualization

Tap to expand

Understanding the Visualization

Input

Grid dimensions m×n with cell costs (i+1)×(j+1)

Rules

Odd moves: right/down only. Even moves: left/up only

Output

Minimum cost to reach (m-1,n-1) or -1 if impossible

Key Takeaway

🎯 Key Insight: Alternating movement constraints severely limit reachability in larger grids

Asked in

G Google 15 M Microsoft 12

This problem requires analyzing alternating movement patterns on a grid. The key insight is that strict movement rules (odd moves: right/down, even moves: left/up) make many destinations unreachable. Best approach is mathematical analysis for small grids. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(4^(m*n))	O(m*n)	Recursively explore all valid paths with alternating movement constraints
Mathematical Analysis	O(1)	O(1)	Analyze grid patterns to determine if destination is mathematically reachable

Brute Force DFS — Algorithm Steps

Step 1: Start DFS from (0,0) with move number 1
Step 2: For odd moves, try right and down; for even moves, try left and up
Step 3: Track minimum cost among all valid paths to destination

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin at (0,0) with move 1 (odd)

Branch

Try all valid moves based on odd/even rule

Explore

Recursively explore each path until destination

Code -

solution.c — C

#include <stdio.h>
#include <limits.h>

int dfs(int row, int col, int moveNum, int m, int n) {
    if (row == m - 1 && col == n - 1) {
        return (row + 1) * (col + 1);
    }
    
    if (row < 0 || row >= m || col < 0 || col >= n) {
        return INT_MAX;
    }
    
    int currentCost = (row + 1) * (col + 1);
    int minCost = INT_MAX;
    
    if (moveNum % 2 == 1) { // Odd move: right or down
        int rightCost = dfs(row, col + 1, moveNum + 1, m, n);
        if (rightCost != INT_MAX && currentCost <= INT_MAX - rightCost) {
            if (currentCost + rightCost < minCost) {
                minCost = currentCost + rightCost;
            }
        }
        int downCost = dfs(row + 1, col, moveNum + 1, m, n);
        if (downCost != INT_MAX && currentCost <= INT_MAX - downCost) {
            if (currentCost + downCost < minCost) {
                minCost = currentCost + downCost;
            }
        }
    } else { // Even move: left or up
        int leftCost = dfs(row, col - 1, moveNum + 1, m, n);
        if (leftCost != INT_MAX && currentCost <= INT_MAX - leftCost) {
            if (currentCost + leftCost < minCost) {
                minCost = currentCost + leftCost;
            }
        }
        int upCost = dfs(row - 1, col, moveNum + 1, m, n);
        if (upCost != INT_MAX && currentCost <= INT_MAX - upCost) {
            if (currentCost + upCost < minCost) {
                minCost = currentCost + upCost;
            }
        }
    }
    
    return minCost;
}

int solution(int m, int n) {
    int result = dfs(0, 0, 1, m, n);
    return result == INT_MAX ? -1 : result;
}

int main() {
    int m, n;
    scanf("%d", &m);
    scanf("%d", &n);
    
    int result = solution(m, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4^(m*n))

Each cell can be visited multiple times with different move numbers, exponential branching

✓ Linear Growth

Space Complexity

O(m*n)

Recursion depth limited by grid size and path length

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~25 min Avg. Time

180 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler