--Shortest Path
#include <iostream>
#define F 99999
#define V 4
using namespace std;
void printShortestPath(int dist[][V]){

    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
        {
            if (dist[i][j] == F)
                cout<<"F\t";
            else
                cout<<dist[i][j]<<"\t";
        }
        cout<<"\n";
    }
}
void Floyd (int graph[][V]){
    int dist[V][V],i,j,k;
    //Khoi tao bang ma tran dist giup luu vet
    for(i=0;i<V;i++){
        for(j=0;j<V;j++){
            dist[i][j]= graph[i][j];
        }
    }
    //Thuạt toan Floyd
    // Kiem tra  dinh k neu do dai tu diem i toi j thong qua k ngan hon thi thay do dai tu i toi j hien tại thanh do dai moi tinh
    for(k=0;k<V;k++){
        for(i=0;i<V;i++){
            for(j=0;j<V;j++){
                if(dist[i][k] != F && dist[k][j] != F && dist[i][j] > dist[i][k] + dist[k][j])
                    dist[i][j]=dist[i][k]+dist[k][j];
            }
        }
    }
    printShortestPath(dist);
}

int main(){
    //Ma trạn ke duong di
    //Duong di cua 1 diem toi chinh no la 0, duong di tu 1 diem i toi diem j ung voi graph[i][j],duong di chua khoi tao ung voi F
    int graph[V][V] = { {0, 5, F, 10},
                        {F, 0, 3, F},
                        {F, F, 0, 1},
                        {F, F, F, 0}
                    };
    Floyd(graph);
}


---coin collect
#include <iostream>
#define n 5
#define m 6
using namespace std;
void trace(int dp[][m]){
    int i=n-1,j=m-1;
    int maptrace[n][m];
    for(int i=0;i<n;i++){
        for(j=0;j<m;j++){
            maptrace[i][j]=0;
        }
    }

    while (i>0 || j>0){
        if(i==0 && j>0){
            maptrace[i][j-1]=1;
            j--;
        }
        else if(j==0 && i>0){
            maptrace[i-1][j]=1;
            i--;
        }
        else if(dp[i][j-1]<dp[i-1][j]){
            maptrace[i-1][j]=1;
            i--;
        }
        else{
            maptrace[i][j-1]=1;
            j--;
        }
    }
    cout<<"...........................................\n";
    cout<<"Duong di cua robot: \n";
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
        {
                cout<<maptrace[i][j]<<"\t";
        }
        cout<<"\n";
    }
}
void coinCollect(int graph[][m]){
    int dp[n][m],i,j;
    for(int i=0;i<n;i++){
        for(j=0;j<m;j++){
            dp[i][j]=0;
        }
    }

    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            if(graph[i][j]==1){
                if(i==0&&j==0)
                    dp[i][j]=1;
                else if (i - 1 < 0)
                        dp[i][j] = dp[i][j - 1] + 1;
                else if (j - 1 < 0)
                        dp[i][j] = dp[i - 1][j] + 1;
                else
                        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + 1;
            }
            else
                {
                    if (i == 0 && j == 0) dp[i][j] = 0;
                    else if (i - 1 < 0)
                        dp[i][j] = dp[i][j - 1];
                    else if (j - 1 < 0)
                        dp[i][j] = dp[i - 1][j];
                    else
                        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
        }
    }
    cout<<"Bang trong so duong di cua robot:\n";
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
        {
                cout<<dp[i][j]<<"\t";
        }
        cout<<"\n";
    }
    trace(dp);
}

int main(){
    int graph[n][m]={{0,0,0,0,1,0},
                      {0,1,0,1,0,0},
                      {0,0,0,1,0,1},
                      {0,0,1,0,0,1},
                      {1,0,0,0,1,0}};
    coinCollect(graph);
}