Finding minimum path from source to destination by changing height of squares

Question

We have NXM grid. One square of the grid is source and one is destination. Each square of grid including source and destination have some elevation(an integer from value 0-9). We have to find a minimum cost path from source to destination satisying following restrictions:

1. The path must be continuous i.e. between adjacent squares only (not diagonal adjacency).
2. One can go from higher elevation to lower elevation only.

The elevation of any square can be increased or decreased. The amount by which elevation changes is counted as cost. If elevation does not change, it is taken as zero cost. So total cost of path from source to destination is the change in elevations of the squares that comes in the path. Moreover elevation of source can't be changed but that of destination can be.

I tried to apply some algorithm like Djikstra and APSP but could not reach any solution. Please help me in this problem.

Answer 1

This is an example of simple shortest distance problem with another dimension, try to formulate the problem like this, cost[n][m][max_height] = {INFINITY};

cost[srcX][srcY][ height[srcX][srcY] ] = 0;

now cost[x+1][y][ht] = min(cost[x+1][y][ht], cost[x][y][q_ht] + (q_ht - ht) ) for q_ht varies from max_height to ht. The idea is to reach at (x+1,y,ht) with least cost from any allowable heights(ie height >= ht). This again we need to calculate for for all ht(0 to max_height). The full implementation is down here:-

#define HIGHVAL 100000000
#define XI (x + a[i])
#define YI (y + b[i])

int n,m;

bool isvalid(int x,int y)
{
    return (x>=0 && y>=0 && x<n && y<m);
}

int main()
{

    int pondX, pondY;
    int farmX, farmY;

    cin>>n>>m>>pondX>>pondY>>farmX>>farmY;
    pondX--, pondY--, farmX--, farmY--;

    int height[n][m];
    string s;

    for(int i=0; i<n; i++)
    {
        cin>>s;
        for(int j=0; j<m; j++)
            height[i][j] = (int)(s[j] - '0');
    }

    int ht = height[pondX][pondY];
    int cost[n][m][ht+1];
    bool visited[n][m];

    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            for(int k=0; k<ht+1; k++)
                cost[i][j][k] = HIGHVAL;

    cost[pondX][pondY][ht] = 0;
    int a[4]= {0,0,1,-1};
    int b[4]= {1,-1,0,0};

    int ci = pondX, cj = pondY;
    queue<int> qx;
    queue<int> qy;

    visited[pondX][pondY] = 1;

    memset(visited, 0, sizeof(visited));
    qx.push(pondX);
    qy.push(pondY);

    while(qy.size())
    {
        int x = qx.front();
        int y = qy.front();

        qx.pop();
        qy.pop();

        for(int i=0; i<4; i++)
        {
            int temp = 0;
            if(isvalid(XI, YI))
            {
                if(!visited[XI][YI])
                {
                    qx.push(XI);
                    qy.push(YI);
                    visited[XI][YI] = 1;
                    temp = 1;
                }

                for(int j=ht; j>=0; j--)
                {
                    int q = HIGHVAL;
                    for(int k=ht; k>=j; k--)
                    {
                        q = min(q, cost[x][y][k] + abs(j - height[XI][YI]));
                    }

                    if(cost[XI][YI][j] > q)
                    {
                        cost[XI][YI][j] = q;

                        if(visited[XI][YI] && !temp)
                        {
                            qx.push(XI);
                            qy.push(YI);
                        }
                    }
                }
            }

        }
    }

    int ans=HIGHVAL;
    for(int i=0; i<=ht; i++)
        ans = min(ans, cost[farmX][farmY][i]);

    cout<<ans;
    //cout<<" "<<n<<m;
    return 0;

}