minimum cost to reach destination through tunnels

Question

Recently I faced a problem in the interview and not able to answer it. Any help will be appreciated.

Given a two dimensional grid (1 <= row <= 10^9 && 1 <= col <= 10^9) and starting and ending coordinates. we can only go to the four adjacent cells and it cost 1 unit. we also have N tunnels (1 <= N <= 200) whose starting and ending coordinates are given and if we go through the tunnel it costs k unit (1 <= k <= 10^9).

Note: It is not necessary to take tunnels but if we take one it costs k unit of energy per tunnel taken.

we have to find the minimum cost to reach the destination from the starting coordinate.

starting coordinate (1 <= sx, sy <= 10^9)

destination coordinate (1 <= fx, fy <= 10^9)

Answer 1

As chmike mentioned, the question can first be transformed into a graph. Then Djikstra's algorithm for finding shortest paths can be used. Here's is my code -

#include<bits/stdc++.h>
using namespace std;

#define int long long int

const int N = 402;
int dp[N][N];
pair<int,int> g[N];
int dist[N];
bool vis[N];

int32_t main(){
    int k,a,b,c,d,n,p,q,r,s,index,nodes,val;
    cin>>k>>a>>b>>c>>d>>n;
    index = 2;
    nodes = 2*n+1;
    for(int i=1;i<=nodes;i++)
        dist[i] = INT_MAX;
    memset(vis,false,sizeof(vis));
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<=nodes;i++)
        dp[i][i] = 0;
    g[0] = {a,b};
    g[1] = {c,d};
    dp[0][1] = dp[1][0] = abs(a-c)+abs(b-d);
    for(int i=0;i<n;i++){
        cin>>p>>q>>r>>s;
        dp[index][index+1] = k;
        dp[index+1][index] = k;
        g[index] = {p,q};
        g[index+1] = {r,s};
        for(int j=0;j<index;j++){
            val = abs(p-g[j].first)+abs(q-g[j].second);
            dp[j][index] = dp[index][j] = val;
            val = abs(r-g[j].first)+abs(s-g[j].second);
            dp[j][index+1] = dp[index+1][j] = val;
        }
        index += 2;
    }
    for(int i=0;i<=nodes;i++){
        int v = -1;
        for(int j=0;j<=nodes;j++){
            if(!vis[j] && (v == -1 || dist[j] < dist[v]))
                v = j;
        }
        if(dist[v] == INT_MAX)
            break;
        vis[v] = true;
        for(int j=0;j<=nodes;j++)
            dist[j] = min(dist[j], dist[v]+dp[v][j]);
    }
    cout<<dist[1];

    return 0;
}

Answer 2

you can use dynamic programming

    #include <bits/stdc++.h>
using namespace std;
#define type long long

int main()
{ //k i sost of travelling through tunnel
//sx and sy are starting coordinates
//fx and fy are ending coordinates

//n are number of tunnels
    int k, sx, sy, fx ,fy,n;
    cin>>k>>sx>>sy>>fx>>fy>>n;
vector<vector<int>> arr(n, vector<int>(4,0));
map<pair<int, int> , pair<int,int>> mp;

//taking inputof tunnel elements and storing it in a map
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<4; j++)
             cin>>arr[i][j];

    pair<int,int> a,b;
    a= pair<int,int> (arr[i][0], arr[i][1]);
    b= pair<int, int> (arr[i][2], arr[i][3]);

    mp[a] = b;
    mp[b] =a;
    }//cin the elements

//function

vector<vector<type>> dp (fx+1, vector<type>(fy+1,LONG_LONG_MAX));
dp[fx][fy] =0; //end
for(int i= fx; i>=0; i--)
{
    for(int j= fy; j>=0; j--)
    {
        //go down
        if(j+1< fy)
        {
            dp[i][j] = min(dp[i][j] , dp[i][j+1]+1 );
        }
       
        //go right
        if(i+1< fx)
        {
            dp[i][j] = min(dp[i][j] , dp[i+1][j]+1 );
        }
        //tunnel
        if(mp.find(pair<int, int> (i,j))!= mp.end())
        {
            pair<int, int> temp= mp[pair<int, int> (i,j)];
            int a= temp.first, b= temp.second;

            if(dp[a][b]!= LONG_LONG_MAX)
            {
                dp[i][j] = min(dp[i][j] , dp[a][b]+ k );
            }
        }
    }
}//

cout<<dp[sx][sy]<<'\n';

}

here i have used dp the array dp is 2-d matrix that saves the cost to reach fx, fy. we start from bottom up approach, at each cell we find the minimum cost to reach the end.

1. we check the cost to reach by stepping 1 cell downward i.e. from dp[i][j] to dp[i][j+1] .
2. then we check the right cell by dp[i+1][j]
3. we see if tunnel is present.

Answer 3

The problem needs to be transposed into a graph with a weight given to each vertex. Once we have done that, we can use the Dijkstra algorithm to find the shortest path.

Solving the problem thus boils down to transposing the problem into a graph with weighted vertices.

We can go from any cell to any other cell without going through a tunnel. The cost is then the manhattan distance. When the coordinate of a cell c1 is (x1,y1) and another cell c2 is (x2,y2), the manhattan distance between c1 and c2 is d=abs(x2-x1)+abs(y2-y1).

The nodes of the graph will correspond to the starting cell, the final cell, and every tunnel exit cells. The number of nodes in the graph is 2 + n where n is the number of tunnels.

There is a vertex between every node. The weight of a vertex to the final node is simply the manhattan distance. The weight of a vertex to a tunnel exit node is the manhattan distance to the tunnel entry cell plus the weight k associated to the tunnel.

This yields a graph that we can now solve using the Dijkstra algorithm to find the shortest path.