Đường đi chi phí nhỏ nhất cho phép đi 4 hướng trong C++

Cho ma trận 2D, mỗi ô có chi phí. Tìm đường đi từ góc trên trái đến góc dưới phải (cho phép đi lên, xuống, trái, phा) với tổng chi phí nhỏ nhất.

Ví dụ: Ma trận 5x5 cho trước → kết quả 340.

Giải thuật Dijkstra

• Dùng priority queue (min-heap) lưu (distance, x, y).
• Khởi tạo distance[0][0] = grid[0][0], các ô khác = INF.
• Lấy ô có distance nhỏ nhất, relax 4 hàng xóm.
• Trả về distance[row-1][col-1].

Ví dụ (C++)

#include <bits/stdc++.h>
using namespace std;
#define ROW 5
#define COL 5

class cell {
public:
    int x, y, distance;
    cell(int x, int y, int d): x(x), y(y), distance(d) {}
};
bool operator<(const cell& a, const cell& b){
    if(a.distance==b.distance){
        if(a.x!=b.x) return a.x<b.x;
        return a.y<b.y;
    }
    return a.distance<b.distance;
}

bool isOk(int i, int j){ return i>=0 && i<COL && j>=0 && j<ROW; }

int solve(int grid[ROW][COL], int row, int col){
    int matrix[row][col];
    for(int i=0;i<row;i++) for(int j=0;j<col;j++) matrix[i][j]=INT_MAX;
    int dx[]={-1,0,1,0}, dy[]={0,1,0,-1};
    set<cell> st;
    st.insert(cell(0,0,0));
    matrix[0][0]=grid[0][0];
    while(!st.empty()){
        cell k=*st.begin(); st.erase(st.begin());
        for(int i=0;i<4;i++){
            int x=k.x+dx[i], y=k.y+dy[i];
            if(!isOk(x,y)) continue;
            if(matrix[x][y]>matrix[k.x][k.y]+grid[x][y]){
                if(matrix[x][y]!=INT_MAX) st.erase(st.find(cell(x,y,matrix[x][y])));
                matrix[x][y]=matrix[k.x][k.y]+grid[x][y];
                st.insert(cell(x,y,matrix[x][y]));
            }
        }
    }
    return matrix[row-1][col-1];
}

int main(){
    int grid[ROW][COL]={ {32,101,66,13,19},
        {11,14,48,158,7},
        {101,114,175,12,34},
        {89,126,42,21,141},
        {100,33,112,42,21} };
    cout<<solve(grid,ROW,COL);
}

Đầu ra

340