Geek asks and answers

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

We have an NXM grid. One square of the grid is the source, and one is the destination. Each square of the grid, including the source and destination, has a certain height (an integer from the value 0-9). We must find the path with the lowest cost from source to destination, observing the following restrictions:

  • The path must be continuous, i.e. only between adjacent squares (not diagonal adjacency).
  • You can go from a higher mark to a lower mark.

The height of any square can be increased or decreased. The amount by which elevation changes are accounted for as value. If the height does not change, it is taken for zero . Thus, the total cost of the path from the source to the destination is the change in the height of the squares that go along the path. In addition, the height of the source cannot be changed, but the destination can be .

I tried to apply some algorithm such as Djikstra and APSP, but could not reach any solution. Please help me with this problem.

+3
source share
3 answers

, , , [n] [m] [max_height] = {INFINITY};

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

[x + 1] [y] [ht] = min ( [x + 1] [y] [ht], [x] [y] [q_ht] + (q_ht - ht)) q_ht max_height ht. (x + 1, y, ht) (, height >= ht). ht ( 0 max_height). : -

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

}
+1

, , .

, Dijkstra (-like) , , . = 0, , .

: . , , .

" " :

  • , (.. ). , H .
  • . .
  • , . , ( ). , H .
  • . = 0 ( ), , .
  • , . , , , .

( *). ( ).

"" , . , .

, . () H, .

, log(N) * N * M, N - , M - ( ), () H ^ 2.

, . - . , - , .

+1

" ", -, , , . -, , - - . , "" "" . , , . , . , , , . , . , " ", @valdo, .

With this understanding, you can use almost any standard path-finding algorithm in a simple way.

0
source

More articles:


All Articles