Finding the Best Vertical Path in a Grid (with Jumps and Weights)

In many grid-based problems, you need to choose exactly one column in each row to form a path.
But not all columns are equal — some cells are better (think “free road”), others are worse (think “toll road”), and some are blocked.

In our example:

X = good cell (free road)
Y = allowed but less preferred cell (toll road)
. = blocked cell (cannot use)

Our goal:

Pick a column in every row so that we have a continuous path from top row to bottom row.
Minimize the number of column changes (jumps) as we go from one row to the next.
If two paths have the same number of jumps, choose the one with fewer Y cells.
If there’s still a tie, choose the leftmost path (smallest column index).

Step 1: Understanding “jumps”

A jump happens when you switch from one column to a different column in the next row.
For example, this path has 1 jump:

Row 0: choose column 2
Row 1: choose column 2 (no jump)
Row 2: choose column 5 (JUMP!)

Step 2: Our DP Table: `min_jumps` and `previous_choice`

We use two tables:

min_jumps[i][j] → a pair (jump_count, y_count) meaning:
minimum jumps and minimum Y count needed to reach row i at column j.
previous_choice[i][j] → the column index from the previous row that gave us this optimal result.

This lets us do dynamic programming row by row:

Start with the first row (min_jumps[0][j] = (0, y_count) if that cell is usable).
For each next row, try all possible previous columns and choose the best one based on our priority:

Step 3: The Code

import math

infinity = math.inf

def find_best_path(grid, allowed):
    """
    Finds the best column path through a grid of 'X', 'Y', '.' by minimizing:
    1. Number of jumps (column changes between consecutive rows)
    2. Number of Y cells (less preferred but allowed)
    3. Column index (lower column chosen in case of tie)

    Parameters:
        grid (list[list[str]]): 2D grid representing rows and columns
                                'X' = preferred cell
                                'Y' = less preferred cell (penalty)
                                '.' = blocked cell (not allowed)
        allowed (set): set of allowed cell types (e.g., {'X', 'Y'})

    Returns:
        path (list[int]): Best column chosen for each row
        min_jumps (int): Minimum number of column changes (jumps)
        min_y_count (int): Minimum number of 'Y' cells encountered
    """

    num_rows = len(grid)      # Number of rows
    num_cols = len(grid[0])   # Number of columns per row

    # min_jumps[i][j] = [jump_count, y_count]
    # jump_count = min number of jumps required to reach (i, j)
    # y_count = number of Y cells taken along the path
    min_jumps = [
        [[infinity, 0] for _ in range(num_cols)]
        for _ in range(num_rows)
    ]

    # previous_choice[i][j] = column index chosen in previous row for best path
    previous_choice = [[-1] * num_cols for _ in range(num_rows)]

    # --- Step 1: Initialize first row ---
    for j in range(num_cols):
        if grid[0][j] != '.':   # Can select only non-blocked cells
            min_jumps[0][j][0] = 0   # No jumps needed for first row

    # --- Step 2: Precompute Y counts for each valid cell ---
    for i in range(num_rows):
        for j in range(num_cols):
            if grid[i][j] == 'Y':
                min_jumps[i][j][1] = 1  # Each Y adds penalty of 1

    # --- Step 3: Fill DP table row by row ---
    for i in range(1, num_rows):
        for j in range(num_cols):
            if grid[i][j] == '.':
                continue  # Can't pick blocked cell in this row

            best_col = -1
            best_val = (infinity, 0)

            # Try all possible previous columns k from row i-1
            for k in range(num_cols):
                if min_jumps[i-1][k][0] == infinity:
                    continue  # No path to this previous column

                # Calculate candidate jump + Y cost if we come from k -> j
                min_jump = 1 if j != k else 0
                candidate = (
                    min_jump + min_jumps[i-1][k][0],  # Total jumps
                    min_jumps[i-1][k][1] + min_jumps[i][j][1]  # Total Y count
                )

                # Pick the lexicographically smallest (jumps, Y count, column)
                if (candidate[0], candidate[1], k) < (best_val[0], best_val[1], best_col):
                    best_col = k
                    best_val = candidate

            previous_choice[i][j] = best_col
            min_jumps[i][j] = best_val

    # Debug: Print DP tables
    for row in min_jumps:
        print(row)
    print()
    for row in previous_choice:
        print(row)

    # --- Step 4: Find best column in last row ---
    last_row = min_jumps[-1]
    best_last_row_res = min(
        [(last_row[col][0], last_row[col][1], col) for col in range(num_cols)]
    )
    jump, ycount, best_end_col = best_last_row_res

    # --- Step 5: Backtrack to reconstruct path ---
    path = [best_end_col]
    for i in range(num_rows - 1, 0, -1):
        best_end_col = previous_choice[i][best_end_col]
        path.append(best_end_col)

    return list(reversed(path)), jump, ycount

import math

infinity = math.inf

def find_best_path(grid, allowed):

"""

Finds the best column path through a grid of 'X', 'Y', '.' by minimizing:

1. Number of jumps (column changes between consecutive rows)

2. Number of Y cells (less preferred but allowed)

3. Column index (lower column chosen in case of tie)

Parameters:

grid (list[list[str]]): 2D grid representing rows and columns

'X' = preferred cell

'Y' = less preferred cell (penalty)

'.' = blocked cell (not allowed)

allowed (set): set of allowed cell types (e.g., {'X', 'Y'})

Returns:

path (list[int]): Best column chosen for each row

min_jumps (int): Minimum number of column changes (jumps)

min_y_count (int): Minimum number of 'Y' cells encountered

"""

num_rows = len(grid) # Number of rows

num_cols = len(grid[0]) # Number of columns per row

# min_jumps[i][j] = [jump_count, y_count]

# jump_count = min number of jumps required to reach (i, j)

# y_count = number of Y cells taken along the path

min_jumps = [

[[infinity, 0] for _ in range(num_cols)]

for _ in range(num_rows)

]

# previous_choice[i][j] = column index chosen in previous row for best path

previous_choice = [[-1] * num_cols for _ in range(num_rows)]

# --- Step 1: Initialize first row ---

for j in range(num_cols):

if grid[0][j] != '.': # Can select only non-blocked cells

min_jumps[0][j][0] = 0 # No jumps needed for first row

# --- Step 2: Precompute Y counts for each valid cell ---

for i in range(num_rows):

for j in range(num_cols):

if grid[i][j] == 'Y':

min_jumps[i][j][1] = 1 # Each Y adds penalty of 1

# --- Step 3: Fill DP table row by row ---

for i in range(1, num_rows):

for j in range(num_cols):

if grid[i][j] == '.':

continue # Can't pick blocked cell in this row

best_col = -1

best_val = (infinity, 0)

# Try all possible previous columns k from row i-1

for k in range(num_cols):

if min_jumps[i-1][k][0] == infinity:

continue # No path to this previous column

# Calculate candidate jump + Y cost if we come from k -> j

min_jump = 1 if j != k else 0

candidate = (

min_jump + min_jumps[i-1][k][0], # Total jumps

min_jumps[i-1][k][1] + min_jumps[i][j][1] # Total Y count

)

# Pick the lexicographically smallest (jumps, Y count, column)

if (candidate[0], candidate[1], k) < (best_val[0], best_val[1], best_col):

best_col = k

best_val = candidate

previous_choice[i][j] = best_col

min_jumps[i][j] = best_val

# Debug: Print DP tables

for row in min_jumps:

print(row)

print()

for row in previous_choice:

print(row)

# --- Step 4: Find best column in last row ---

last_row = min_jumps[-1]

best_last_row_res = min(

[(last_row[col][0], last_row[col][1], col) for col in range(num_cols)]

)

jump, ycount, best_end_col = best_last_row_res

# --- Step 5: Backtrack to reconstruct path ---

path = [best_end_col]

for i in range(num_rows - 1, 0, -1):

best_end_col = previous_choice[i][best_end_col]

path.append(best_end_col)

return list(reversed(path)), jump, ycount

Example Run

grid = [
    ['X', 'X', 'Y', '.', 'X'],
    ['X', '.', 'Y', 'X', '.'],
    ['X', 'Y', 'X', '.', 'X']
]

allowed = {'X', 'Y'}
 
path, min_jump, ycount = find_best_path(grid, allowed)

print("Best column path:", path)
print("Final min_jumps:", min_jump)
print("Final y_count:", ycount)

grid = [

['X', 'X', 'Y', '.', 'X'],

['X', '.', 'Y', 'X', '.'],

['X', 'Y', 'X', '.', 'X']

]

allowed = {'X', 'Y'}

path, min_jump, ycount = find_best_path(grid, allowed)

print("Best column path:", path)

print("Final min_jumps:", min_jump)

print("Final y_count:", ycount)

Output (example):

Best column path: [0, 0, 0]
Final min_jumps: 0
Final y_count: 0

Best column path: [0, 0, 0]

Final min_jumps: 0

Final y_count: 0

Meaning:

We stayed in column 0 for the all rows (no jump).
0 Y count

Visual Explanation

Here’s a shorter, clear version of the explanation with visualization:

Example Grid

Row 0:  X  X  Y  .  X
Row 1:  X  .  Y  X  .
Row 2:  X  Y  X  .  X

X = free cell (no penalty)
Y = allowed but adds +1 penalty
. = blocked

Algorithm in Brief

Initialize Row 0: Set jump count = 0 where cell ≠ ., Y adds y_count=1.
For Each Row:
Final Row: Choose column with smallest (jumps, Y count, column index) and backtrack to build the path.

Result for This Grid

✅ Best Path: [0, 0, 0] (Column 0 for all rows)

Jumps: 0 (no column change)
Y Count: 0 (avoids Y completely)

Visual Path

Row 0: [X]  X   Y   .   X
Row 1: [X]  .   Y   X   .
Row 2: [X]  Y   X   .   X

Row 0: [X] X Y . X

Row 1: [X] . Y X .

Row 2: [X] Y X . X

The algorithm chose column 0 in every row because it has:

No jumps (stays in same column)
No Y cells (minimum penalty)
Lowest column index in case of ties

Why This Approach Works

This approach is efficient because:

We consider all possible columns for each row, so we never miss a better path.
The decision-making is lexicographic: prioritize jumps, then Y count, then leftmost.
It runs in O(R × C²) time (R = rows, C = columns), which is usually fast enough for small/medium grids. For larger grid, we can optimize with heuristics or pruning.

When to Use This

This technique is useful in any problem where:

You need to select exactly one option per row/level.
Each choice has a cost, and you want to minimize a combination of costs.
There is an adjacency relationship between rows (penalty for switching columns).

Examples outside this puzzle could include:

Scheduling problems where switching machines incurs cost.
Choosing routes across layered networks.
Grid-based puzzle solvers (like pathfinding with penalties).

Key Takeaways

Dynamic programming gives us a clean way to evaluate every possible path.
By comparing (jumps, y_count, column) at every step, we guarantee we choose the optimal path.
Backtracking with previous_choice recovers the actual path easily.

This approach can be used anywhere you need to pick one “best” option per row with priorities and penalties.

I hope this tutorial will create a good foundation for you. If you want tutorials on another topic or you have any queries, please send an mail at contact@spatial-dev.guru.

Step 1: Understanding “jumps”

Step 2: Our DP Table: min_jumps and previous_choice

Step 3: The Code

Example Run

Visual Explanation

Example Grid

Algorithm in Brief

Result for This Grid

Visual Path

Why This Approach Works

When to Use This

Key Takeaways

Related Posts

Leave a ReplyCancel reply

Discover more from Spatial Dev Guru

Discover more from Spatial Dev Guru

Step 2: Our DP Table: `min_jumps` and `previous_choice`