Number of Ways to Reach Destination in the Grid - Problem

Imagine you're navigating a grid-based board game where you can only move in straight lines! You start at a source position and need to reach a destination in exactly k moves.

The Challenge: Given an n × m grid (1-indexed), a starting position source [x, y], and a destination dest [x, y], find the number of ways to reach the destination in exactly k steps.

Movement Rules:

You can move from cell [x1, y1] to [x2, y2] if either x1 == x2 (same row) or y1 == y2 (same column)
You cannot stay in the same cell (no self-loops)
Each move counts as exactly 1 step

Goal: Return the total number of distinct paths of length k from source to destination, modulo 10⁹ + 7.

Input & Output

example_1.py — Basic Grid Navigation

$ Input: n = 2, m = 3, k = 3, source = [1, 1], dest = [2, 3]

› Output: 4

💡 Note: There are 4 different ways to reach destination [2,3] from source [1,1] in exactly 3 steps. Some example paths: [1,1] → [1,2] → [2,2] → [2,3], [1,1] → [1,3] → [2,3] → [2,1] → [2,3], etc.

example_2.py — Same Position

$ Input: n = 3, m = 3, k = 2, source = [1, 1], dest = [1, 1]

› Output: 16

💡 Note: To return to the same position in exactly 2 steps, we can move to any of the 4 adjacent cells (2 in same row + 2 in same column), then return. Each of the 4 first moves has 4 possible return moves, giving 4×4 = 16 total paths.

example_3.py — Impossible Case

$ Input: n = 2, m = 2, k = 1, source = [1, 1], dest = [2, 2]

› Output: 0

💡 Note: From [1,1], we can only move to [1,2] or [2,1] in one step (same row or column). We cannot reach [2,2] directly in 1 step since it requires changing both row and column.

Constraints

1 ≤ n, m ≤ 1000
0 ≤ k ≤ 1000
1 ≤ source[0], dest[0] ≤ n
1 ≤ source[1], dest[1] ≤ m
Grid coordinates are 1-indexed

Visualization

Tap to expand

Asked in

G Google 45 ⊞ Microsoft 32 f Meta 28 a Amazon 25

This grid path counting problem is best solved using dynamic programming with memoization. The key insight is that we can model valid moves (same row or column) as state transitions and cache results for repeated subproblems. The optimal solution runs in O(n × m × k) time and handles all edge cases efficiently, making it suitable for the given constraints.

Common Approaches

✓ Dynamic Programming with Memoization (Optimal)

⏱️ Time: O(n * m * k) Space: O(n * m * k)

Enhance the recursive approach with memoization to store results of (position, steps_remaining) states. This eliminates redundant calculations and achieves polynomial time complexity.

Recursive Exploration (Brute Force)

⏱️ Time: O((n+m)^k) Space: O(k)

Use depth-first search to explore every possible sequence of k moves. At each step, try moving to every valid cell (same row or column) and recursively count paths from there.

Dynamic Programming with Memoization (Optimal) — Algorithm Steps

Create a memoization table indexed by (x, y, steps)
Use the same recursive logic as brute force
Before computing, check if result exists in memo table
After computing, store result in memo table
Return memoized result for future identical subproblems

Visualization

Tap to expand

Step-by-Step Walkthrough

First Call

Compute result for state (x,y,k) and store in memo

Cache Hit

When same state appears again, return cached result

Subproblem Overlap

Many paths lead to same intermediate states

Efficiency Gain

Each unique state computed only once

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

#define MOD 1000000007LL
#define MAX_N 101
#define MAX_M 101

static long long dp[MAX_N][MAX_M];
static long long next_dp[MAX_N][MAX_M];

long long numberOfWays(int n, int m, int k, int sx, int sy, int dx, int dy) {
    if (k == 0) {
        return (sx == dx && sy == dy) ? 1LL : 0LL;
    }
    
    // Initialize DP table
    memset(dp, 0, sizeof(dp));
    memset(next_dp, 0, sizeof(next_dp));
    
    // Base case: start at source position
    dp[sx][sy] = 1;
    
    // For each step
    for (int step = 0; step < k; step++) {
        memset(next_dp, 0, sizeof(next_dp));
        
        // For each current position that has ways to reach it
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= m; y++) {
                if (dp[x][y] == 0) continue;
                
                long long ways = dp[x][y];
                
                // Move in same row (different columns)
                for (int new_y = 1; new_y <= m; new_y++) {
                    if (new_y != y) {
                        next_dp[x][new_y] = (next_dp[x][new_y] + ways) % MOD;
                    }
                }
                
                // Move in same column (different rows)
                for (int new_x = 1; new_x <= n; new_x++) {
                    if (new_x != x) {
                        next_dp[new_x][y] = (next_dp[new_x][y] + ways) % MOD;
                    }
                }
            }
        }
        
        // Swap dp arrays
        memcpy(dp, next_dp, sizeof(dp));
    }
    
    return dp[dx][dy];
}

int main(void) {
    int n, m, k;
    int sx, sy, dx, dy;
    char comma;
    
    scanf("%d", &n);
    scanf("%d", &m);
    scanf("%d", &k);
    scanf("%d%c%d", &sx, &comma, &sy);
    scanf("%d%c%d", &dx, &comma, &dy);
    
    printf("%lld\n", numberOfWays(n, m, k, sx, sy, dx, dy));
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n * m * k)

At most n*m*k unique subproblems, each solved once

✓ Linear Growth

Space Complexity

O(n * m * k)

Memoization table stores results for all states plus recursion stack

✓ Linear Space

43.2K Views

Medium-High Frequency

~25 min Avg. Time

1.9K 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

Number of Ways to Reach Destination in the Grid - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Memoization (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler