Minimum Cost Path with Left, Right, Bottom and Up moves allowed - GeeksforGeeks
Given a two dimensional grid, each cell of which contains integer cost which represents a cost to traverse through that cell, we need to find a path from top left cell to bottom right cell by which total cost incurred is minimum.
Note : It is assumed that negative cost cycles do not exist in input matrix.
http://www.geeksforgeeks.org/dynamic-programming-set-6-min-cost-path/
Read full article from Minimum Cost Path with Left, Right, Bottom and Up moves allowed - GeeksforGeeks
Given a two dimensional grid, each cell of which contains integer cost which represents a cost to traverse through that cell, we need to find a path from top left cell to bottom right cell by which total cost incurred is minimum.
Note : It is assumed that negative cost cycles do not exist in input matrix.
struct cell{ int x, y; int distance; cell(int x, int y, int distance) : x(x), y(y), distance(distance) {}};// Utility method for comparing two cellsbool operator<(const cell& a, const cell& b){ if (a.distance == b.distance) { if (a.x != b.x) return (a.x < b.x); else return (a.y < b.y); } return (a.distance < b.distance);}// Utility method to check whether a point is// inside the grid or notbool isInsideGrid(int i, int j){ return (i >= 0 && i < COL && j >= 0 && j < ROW);}// Method returns minimum cost to reach bottom// right from top leftint shortest(int grid[ROW][COL], int row, int col){ int dis[row][col]; // initializing distance array by INT_MAX for (int i = 0; i < row; i++) for (int j = 0; j < col; j++) dis[i][j] = INT_MAX; // direction arrays for simplification of getting // neighbour int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; set<cell> st; // insert (0, 0) cell with 0 distance st.insert(cell(0, 0, 0)); // initialize distance of (0, 0) with its grid value dis[0][0] = grid[0][0]; // loop for standard dijkstra's algorithm while (!st.empty()) { // get the cell with minimum distance and delete // it from the set cell k = *st.begin(); st.erase(st.begin()); // looping through all neighbours for (int i = 0; i < 4; i++) { int x = k.x + dx[i]; int y = k.y + dy[i]; // if not inside boundry, ignore them if (!isInsideGrid(x, y)) continue; // If distance from current cell is smaller, then // update distance of neighbour cell if (dis[x][y] > dis[k.x][k.y] + grid[x][y]) { // If cell is already there in set, then // remove its previous entry if (dis[x][y] != INT_MAX) st.erase(st.find(cell(x, y, dis[x][y]))); // update the distance and insert new updated // cell in set dis[x][y] = dis[k.x][k.y] + grid[x][y]; st.insert(cell(x, y, dis[x][y])); } } } // uncomment below code to print distance // of each cell from (0, 0) /* for (int i = 0; i < row; i++, cout << endl) for (int j = 0; j < col; j++) cout << dis[i][j] << " "; */ // dis[row - 1][col - 1] will represent final // distance of bottom right cell from top left cell return dis[row - 1][col - 1];}http://www.geeksforgeeks.org/dynamic-programming-set-6-min-cost-path/
private static int minCost(int cost[][], int m, int n) { int i, j; int tc[][]=new int[m+1][n+1]; tc[0][0] = cost[0][0]; /* Initialize first column of total cost(tc) array */ for (i = 1; i <= m; i++) tc[i][0] = tc[i-1][0] + cost[i][0]; /* Initialize first row of tc array */ for (j = 1; j <= n; j++) tc[0][j] = tc[0][j-1] + cost[0][j]; /* Construct rest of the tc array */ for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) tc[i][j] = min(tc[i-1][j-1], tc[i-1][j], tc[i][j-1]) + cost[i][j]; return tc[m][n]; }int minCost(int cost[R][C], int m, int n){ if (n < 0 || m < 0) return INT_MAX; else if (m == 0 && n == 0) return cost[m][n]; else return cost[m][n] + min( minCost(cost, m-1, n-1), minCost(cost, m-1, n), minCost(cost, m, n-1) );}