algorithm - 通过更改正方形的高度来找到从源到目的地的最小路径

我们有NXM网格一个方格是源，一个是目的地。每个方格（包括源和目标）都有一些高程（0-9之间的整数）我们必须找到从源到目的地的最低成本路径，并满足以下限制：
路径必须是连续的，即仅在相邻正方形之间（而不是对角线相邻）。
一个人只能从高海拔到低海拔。
任何正方形的高度都可以增加或减少。高程变化的量计入成本如果高程不变，则取零成本。
所以从源头到目的地的路径总成本是路径中的正方形的高度变化此外，源的高程不能更改，但目的地的高程可以更改。
我试图应用一些算法，如djikstra和apsp，但无法得到任何解决方案。请帮我解决这个问题。

最佳答案

这是另一个维度的简单最短距离问题的一个例子，试着用这样的公式来表示这个问题，
成本[n][m][max_height]={infinity}；
成本[srcx][srcy][height[srcx][srcy]]=0；
现在，q-ht的成本[x+1][y][ht]=min（成本[x+1][y][ht]，成本[x][y][q-ht]+（q-ht-ht））从最大高度到高度不等我们的想法是在（x+1，y，ht）以最小的成本从任何允许的高度（即高度>=ht）到达我们需要再次计算所有高度（0到最大高度）全面实施如下：

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

}

关于algorithm - 通过更改正方形的高度来找到从源到目的地的最小路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10668605/