通过隧道到达目的地的最低成本

Question

最近我在面试中遇到了一个问题，无法回答。任何帮助都将不胜感激。

给定一个二维网格(1 <= row <= 10^9 &1 <= <= 10^9)和起始坐标和结束坐标。我们只能去四个相邻的单元，它花费1单位。我们还有N隧道(1 <= N <= 200)，给出了其起始和结束坐标，如果我们穿过隧道，则需要k单元 (1 <= k <= 10^9)。

注：，没有必要采取隧道，但如果我们采取一个，它的成本单位的能量每隧道采取。

我们必须找到最小成本，才能从起始坐标到达目的地。

起始坐标(1 <= sx，sy <= 10^9)

目标坐标(1 <= fx，fy <= 10^9)

Answer 1

这个问题需要转换成一个图，并给出每个顶点的权重。一旦我们这样做了，我们就可以使用Dijkstra算法来找到最短路径。

因此，将问题归结为将问题转化为具有加权顶点的图。

我们可以从任何细胞到任何其他细胞，而不需要穿越隧道。成本是曼哈顿的距离。当单元格c1的坐标为(x1,y1)，而另一个单元格c2为(x2,y2)时，c1与c2之间的曼哈顿距离为d=abs(x2-x1)+abs(y2-y1)。

图中的节点将对应于起始单元、最终单元和每个隧道退出单元。图中节点数为2+n，其中n为隧道数。

每个节点之间都有一个顶点。一个顶点到最后一个节点的重量就是曼哈顿距离。隧道出口节点顶点的重量是隧道入口单元的曼哈顿距离加上与隧道相关的重量k。

这产生了一个图，我们现在可以用Dijkstra算法来求解它，以找到最短的路径。

Answer 2

正如chmike所提到的，这个问题可以首先转化为一个图。在此基础上，提出了一种求解最短路径的算法。这是我的密码-

#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 3

您可以使用动态规划。

    #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';

}

这里我使用了dp，数组dp是二维矩阵，节省了到达fx，fy的成本。我们从自下而上的方法开始，在每个单元中，我们找到了达到终点的最小成本。

，

1. ，我们通过向下的1单元，即从dpi到dpi，来检查达到的成本。
2. ，然后我们通过dpi+1
3. 检查正确的单元，看看是否存在隧道。