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

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Naive Recursive Solution:
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.

Below is the implementation of the approach.

## C++

 // Recursive CPP program to find minimum jumps // to reach last building from first. #include using namespace std;    # define R 4 # define C 3    bool isSafe(int x, int y) {     return (x < R && y < 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) {     // base case     if (x == R - 1 && y == C - 1)         return 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 jumps     return min({down, right, diag}); }    /* Driver program to test above functions */ int main() {     int height[][C] = { { 5, 4, 2 },                        { 9, 2, 1 },                        { 2, 5, 9 },                        { 1, 3, 11 } };        cout << minJump(height, 0, 0);     return 0; }

## Java

 // Recursive Java program // to find minimum jumps // to reach last building  // from first. class GFG {            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));     }            // Driver program      public static void main(String[] args)     {         int height[][] = { { 5, 4, 2 },                            { 9, 2, 1 },                            { 2, 5, 9 },                            { 1, 3, 11} };                System.out.println(minJump(height, 0, 0));     } }    // This article is contributed by Prerna Saini.

## Python3

 # Recursive Python3 program to find minimum jumps # to reach last building from first. R = 4 C = 3    def isSafe(x, y):     return (x < R and y < C)    # Returns minimum jump path from  # (0, 0) to (m, n) in hight[R][C] def minJump(height, x, y):        # base case     if (x == R - 1 and y == C - 1):         return 0        # Find minimum jumps if we go     # through diagonal     diag = 10**9     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     down = 10**9     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     right = 10**9     if (isSafe(x, y + 1)):         right = (minJump(height, x, y + 1) +                       abs(height[x][y] -                           height[x][y + 1]))        # return minimum jumps     return min([down, right, diag])    # Driver Code height = [ [ 5, 4, 2 ],            [ 9, 2, 1 ],            [ 2, 5, 9 ],            [ 1, 3, 11 ] ]    print(minJump(height, 0, 0))    # This code is contributed by mohit kumar

## C#

 // Recursive C# program // to find minimum jumps // to reach last building  // from first. using System;    class GFG {            static bool 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 = int.MaxValue;                    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 = int.MaxValue;                    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 = int.MaxValue;                    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));     }            // Driver code     public static void Main()     {         int [,]height = {{5, 4, 2},                         {9, 2, 1},                         {2, 5, 9},                         {1, 3, 11}};                Console.Write(minJump(height, 0, 0));     } }    // This code is contributed by nitin mittal

## PHP



Output :

12

Time complexity of this solution is exponential.

Dynamic Programming Solution:
If we draw recursion tree of above recursive solution, we can observe overlapping subproblems. Since the problem has overlapping subproblems, we can solve it efficiently using Dynamic Programming. Below is Dynamic Programming based solution.

## C++

 // A Dynamic Programming based CPP program to find // minimum jumps to reach last building from first. #include using namespace std;    #define R 4 #define C 3    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]; }    /* Driver program to test above functions */    int main() {     int height[][C] = { { 5, 4, 2 },                        { 9, 2, 1 },                        { 2, 5, 9 },                        { 1, 3, 11 } };     memset(dp, -1, sizeof(dp));     cout << minJump(height, 0, 0);     return 0; }

## Java

 // A Dynamic Programming based Java program to find // minimum jumps to reach last building from first. import java.util.*;    class GFG  {        static int R = 4;     static int C = 3;        static boolean isSafe(int x, int y)      {         return (x < R && y < C);     }        // Lookup table used for memoization.     static int[][] dp = new int[R][C];        /* Returns minimum jump path from (0, 0) to (m, n)     in hight[R][C]*/     static int minJump(int height[][], 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 = 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 jump         dp[x][y] = Math.min(Math.min(down, right), diag);         return dp[x][y];     }        /* Driver program to test above functions */     public static void main(String[] args)     {         int height[][] = {{5, 4, 2},         {9, 2, 1},         {2, 5, 9},         {1, 3, 11}};         for (int i = 0; i < R; i++) {             for (int j = 0; j < C; j++) {                 dp[i][j] = -1;             }         }         System.out.println(minJump(height, 0, 0));     } }    /* This code is contributed by PrinciRaj1992 */

## Python

 # A Dynamic Programming based Python program to find # minimum jumps to reach last building from first.    R = 4 C = 3    def isSafe( x, y):        return (x < R and y < C)    # Lookup table used for memoization. dp = [[-1 for i in range(C)] for i in range(R)]    # Returns minimum jump path from (0, 0) to (m, n) # in hight[R][C]*/ def minJump(height, x, y):       # if we visited it before     if (dp[x][y] != -1):         return dp[x][y]        if (x == R - 1 and y == C - 1):         return (dp[x][y] == 0)    # Find minimum jumps if we go through diagonal     diag = 10**9     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     down =10**9     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     right =10**9     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]    # Driver code     height=[[ 5, 4, 2 ],     [ 9, 2, 1 ],     [ 2, 5, 9 ],     [ 1, 3, 11 ]]    print(minJump(height, 0, 0))    # This code is contributed by mohit kumar 29

## C#

 // A Dynamic Programming based C# program to find // minimum jumps to reach last building from first. using System;    class GFG  {        static int R = 4;     static int C = 3;        static Boolean isSafe(int x, int y)      {         return (x < R && y < C);     }        // Lookup table used for memoization.     static int[,] dp = new int[R,C];        /* Returns minimum jump path from (0, 0) to (m, n)     in hight[R,C]*/     static int minJump(int [,]height, 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.MaxValue;         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 = int.MaxValue;         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 = int.MaxValue;         if (isSafe(x, y + 1))          {             right = minJump(height, x, y + 1)                     + Math.Abs(height[x,y] - height[x,y + 1]);         }            // return minimum jump         dp[x,y] = Math.Min(Math.Min(down, right), diag);         return dp[x,y];     }        /* Driver code */     public static void Main(String[] args)     {         int [,]height = {{5, 4, 2},         {9, 2, 1},         {2, 5, 9},         {1, 3, 11}};         for (int i = 0; i < R; i++) {             for (int j = 0; j < C; j++) {                 dp[i,j] = -1;             }         }         Console.WriteLine(minJump(height, 0, 0));     } }    // This code is contributed by 29AjayKumar

Output:

12

Time complexity: (R*C)

GeeksforGeeks has prepared a complete interview preparation course with premium videos, theory, practice problems, TA support and many more features. Please refer Placement 100 for details

My Personal Notes arrow_drop_up

Check out this Author's contributed articles.

If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please Improve this article if you find anything incorrect by clicking on the "Improve Article" button below.
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}