Min Cost Path

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
using namespace std;

// Direction flags (using bits to allow multiple directions)
enum Direction {
    NONE = 0,
    DIAGONAL = 1,  // 001
    UP = 2,        // 010
    LEFT = 4       // 100
};

// Position in the grid
struct Position {
    int row;
    int col;

    Position(int r, int c) : row(r), col(c) {}

    // Needed for storing positions in a vector path
    bool operator==(const Position& other) const {
        return row == other.row && col == other.col;
    }
};

// Path representation
typedef vector<Position> Path;

// Function to find all minimum cost paths from (0,0) to (m,n)
int findAllMinCostPaths(vector<vector<int>>& cost, int m, int n, vector<Path>& allPaths) {
    // Create dp table for minimum costs
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));

    // Create a table to track all directions that lead to minimum cost
    // We use bit flags to represent multiple directions
    vector<vector<int>> dirs(m + 1, vector<int>(n + 1, NONE));

    // Base case: cost to reach (0,0) is the cost of the cell itself
    dp[0][0] = cost[0][0];

    // Fill the first column (can only come from above)
    for (int i = 1; i <= m; i++) {
        dp[i][0] = dp[i-1][0] + cost[i][0];
        dirs[i][0] = UP;
    }

    // Fill the first row (can only come from left)
    for (int j = 1; j <= n; j++) {
        dp[0][j] = dp[0][j-1] + cost[0][j];
        dirs[0][j] = LEFT;
    }

    // Fill the rest of the dp table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // Get costs from all three directions
            int fromAbove = dp[i-1][j];
            int fromLeft = dp[i][j-1];
            int fromDiagonal = dp[i-1][j-1];

            // Find the minimum cost among all directions
            int minCost = min({fromAbove, fromLeft, fromDiagonal});

            // Set the cost for current cell
            dp[i][j] = cost[i][j] + minCost;

            // Track all directions that lead to the minimum cost
            if (fromDiagonal == minCost) {
                dirs[i][j] |= DIAGONAL;  // Set the DIAGONAL bit
            }
            if (fromAbove == minCost) {
                dirs[i][j] |= UP;  // Set the UP bit
            }
            if (fromLeft == minCost) {
                dirs[i][j] |= LEFT;  // Set the LEFT bit
            }
        }
    }

    // Clear the paths vector
    allPaths.clear();

    // Define a recursive function to find all paths
    function<void(int, int, Path&)> findPaths = [&](int i, int j, Path& currentPath) {
        // Add current position to path
        currentPath.push_back(Position(i, j));

        // If we've reached the origin, we've found a complete path
        if (i == 0 && j == 0) {
            // Reverse path and add to results
            Path completePath = currentPath;
            reverse(completePath.begin(), completePath.end());
            allPaths.push_back(completePath);
        } else {
            // Try all possible directions from current cell
            if (dirs[i][j] & DIAGONAL) {
                findPaths(i-1, j-1, currentPath);
            }
            if (dirs[i][j] & UP) {
                findPaths(i-1, j, currentPath);
            }
            if (dirs[i][j] & LEFT) {
                findPaths(i, j-1, currentPath);
            }
        }

        // Backtrack by removing current position
        currentPath.pop_back();
    };

    // Start the recursive search from the destination
    Path currentPath;
    findPaths(m, n, currentPath);

    // Return the minimum cost
    return dp[m][n];
}

// Function to print a single path with costs
void printPath(const Path& path, const vector<vector<int>>& cost) {
    int runningSum = 0;
    for (const auto& pos : path) {
        runningSum += cost[pos.row][pos.col];
        cout << "(" << pos.row << "," << pos.col << ") -> Cost: " << cost[pos.row][pos.col]
             << " (Running total: " << runningSum << ")" << endl;
    }
}

int main() {
    // Example cost matrix with multiple equal-cost paths
    vector<vector<int>> cost = {
        {1, 3, 1},
        {2, 2, 2},
        {4, 1, 1}
    };

    // Get dimensions of the matrix (0-indexed)
    int m = cost.size() - 1;
    int n = cost[0].size() - 1;

    // Vector to store all minimum cost paths
    vector<Path> allPaths;

    // Calculate minimum cost and get all paths
    int minCost = findAllMinCostPaths(cost, m, n, allPaths);

    // Print the minimum cost
    cout << "Minimum cost to reach (" << m << "," << n << ") from (0,0): " << minCost << endl;

    // Print all minimum cost paths
    cout << "Found " << allPaths.size() << " minimum cost path(s):" << endl;
    for (int i = 0; i < allPaths.size(); i++) {
        cout << "Path " << (i + 1) << ":" << endl;
        printPath(allPaths[i], cost);
        cout << endl;
    }

    return 0;
}