💻 Minimum Cost Path in Grid with Diagonal Moves

Navigate the cost grid using DP to find the cheapest path from top-left to bottom-right — allowing right, down, and diagonal steps!

🗺️ The Cost Navigator's Challenge

🎯 The Challenge:

You are given a 2D grid of size R x C where each cell contains a non-negative integer representing the cost to step into that cell. Find the minimum cost to reach the bottom-right cell (R-1, C-1) from the top-left cell (0, 0), moving right, down, or diagonally.

Problem Specifications

  • Input: First line: R C (1 ≤ R, C ≤ 1000). Next R lines: C integers (0 ≤ grid[i][j] ≤ 10^5).
  • Output: Single integer: minimum total cost to (R-1, C-1).

Example: Input 1

1 3
3 2 1

Output: 6

Example: Input 2

2 2
0 1
1 0

Output: 0 (diagonal path)

🔄 Dynamic Programming Strategy

Key Idea

  1. dp[i][j] = minimum cost to reach (i,j) from (0,0).
  2. Base: dp[0][0] = grid[0][0].
  3. For others: dp[i][j] = grid[i][j] + min( dp[i][j-1] if j>0, dp[i-1][j] if i>0, dp[i-1][j-1] if i>0 j>0 ).
  4. Fill row-by-row, left-to-right.

Note: Result is dp[R-1][C-1]. Handles boundaries naturally.

DP Fill

Time: O(R * C)

Dijkstra (General)

O((R*C) log(R*C)) — overkill here

🔍 Step-by-Step DP Demo

Ready. Use controls below to start demo.

Cost Grid

DP Table State (min cost to cell)

Min cost will appear here

Progress Tracker

1. Set dp[0][0] = grid[0][0]
2. Fill first row (only right moves)
3. Fill first column (only down moves)
4. For each inner cell: min from left/up/diagonal + grid[i][j]
5. Proceed row-by-row
6. Result at dp[R-1][C-1]

🎮 Build Your Min Cost Path Finder

Enter R, C, grid and press Compute

Examples

1x3: 3 2 1
→ 6
2x2: 0 1 / 1 0
→ 0

📊 Analysis & Optimization

Time

O(R * C)

Single pass over grid.

Space

O(R * C)

DP table; optimizable to O(C) with 1D array.

Optimization Ideas

  • Use 1D DP array, updating in-place per row.
  • For large R/C=1000, ensure fast I/O in C++ (e.g., std::cin with std::ios::sync_with_stdio(false)).
  • Since costs non-negative and DAG, DP is optimal.