Minimum jumps to reach last building in a matrix

https://www.geeksforgeeks.org/minimum-jumps-to-reach-last-building-in-a-matrix/

Given a matrix containing an integer value, In which each cell of the matrix represents height of building. Find minimum jumps needed reach from First building (0, 0) to last (n-1, m-1). Jump from a cell to next cell is absolute difference between two building heights.
Examples :

Input :  int height[][] = {{ 5, 4, 2 },
                           { 9, 2, 1 },
                           { 2, 5, 9 },
                           { 1, 3, 11}}; 
Output : 12
The minimum jump path is 5 -> 2 -> 5
-> 11. Total jumps is 3 + 3 + 6 = 12.

DFS + cache

Time complexity: (R*C)

bool isSafe(int x, int y)

{

    return (x < R && y < C);

}

  

// Lookup table used for memoization.

int dp[R][C];

  

/* Returns minimum jump path from (0, 0) to (m, n)

   in hight[R][C]*/

int minJump(int height[R][C], int x, int y)

{

    // if we visited it before

    if (dp[x][y] != -1)

        return dp[x][y];

  

    if (x == R - 1 && y == C - 1)

        return (dp[x][y] = 0);

  

    // Find minimum jumps if we go through diagonal

    int diag = INT_MAX;

    if (isSafe(x + 1, y + 1))

        diag = minJump(height, x + 1, y + 1) +

           abs(height[x][y] - height[x + 1][y + 1]);

  

    // Find minimum jumps if we go through down

    int down = INT_MAX;

    if (isSafe(x + 1, y))

        down = minJump(height, x + 1, y) + 

             abs(height[x][y] - height[x + 1][y]);

  

    // Find minimum jumps if we go through right

    int right = INT_MAX;

    if (isSafe(x, y + 1))

        right = minJump(height, x, y + 1) + 

              abs(height[x][y] - height[x][y + 1]);

  

    // return minimum jump

    dp[x][y] = min({down, right, diag});

    return dp[x][y];

}

The above problem can be solve easily by using recursion. The path to reach (m, n) must be through one of the 3 cells: (m-1, n-1) or (m-1, n) or (m, n-1). So minimum jump to reach (m, n) can be written as “minimum jump of the 3 cells plus current jump.

Time complexity of this solution is exponential.

    static boolean isSafe(int x, int y)

    {

        return (x < 4 && y < 3);

    }

      

    // Returns minimum jump

    // path from (0, 0) to 

    // (m, n) in hight[R][C]

    static int minJump(int height[][], int x,

                                       int y)

    {

        // base case

        if (x == 4 - 1 && y == 3 - 1)

            return 0;

      

        // Find minimum jumps 

        // if we go through 

        // diagonal

        int diag = Integer.MAX_VALUE;

          

        if (isSafe(x + 1, y + 1))

            diag = minJump(height, x + 1, y + 1) +

                   Math.abs(height[x][y] - height[x + 1][y + 1]);

      

        // Find minimum jumps

        // if we go through

        // down

        int down = Integer.MAX_VALUE;

          

        if (isSafe(x + 1, y))

            down = minJump(height, x + 1, y) +

                   Math.abs(height[x][y] - height[x + 1][y]);

      

        // Find minimum jumps

        // if we go through right

        int right = Integer.MAX_VALUE;

          

        if (isSafe(x, y + 1))

            right = minJump(height, x, y + 1) +

                    Math.abs(height[x][y] - height[x][y + 1]);

      

        // return minimum jumps

        return Math.min(down, Math.min(right, diag));

    }