Advertisement
naeem043

C DP Rock Climbing with path

Aug 3rd, 2018
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.64 KB | None | 0 0
  1. #include<stdio.h>
  2. int min(int a, int b,int c)
  3. {
  4.     int x = a<b ? a : b;
  5.     return x < c ? x : c;
  6. }
  7. int dp[5][7], best_path[5];
  8. int main()
  9. {
  10.     int arr[5][6] = { {0,0,0,0,0,0 }, { 0,3,2,5,4,8 }, { 0,5,7,5,6,1 }, { 0,4,4,6,2,3 }, { 0,2,8,9,5,8 } };
  11.     int i,j,k=0,m,n;
  12.  
  13.     for (i = 0; i <5; i++)
  14.     {
  15.         dp[i][0] = 9999;
  16.         dp[i][6] = 9999;
  17.     }
  18. //================
  19.     for (i = 1; i <5; i++)
  20.     {
  21.         for (j = 1; j <6; j++)
  22.         {
  23.             dp[i][j] = arr[i][j] + min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]);
  24.  
  25.         }
  26.  
  27.     }
  28.  
  29.         int flag=99999;
  30.  
  31.         for(j = 1; j <6; j++)
  32.         {
  33.             if(dp[4][j]<flag)
  34.             {
  35.                  flag = dp[4][j];
  36.  
  37.                   best_path[k] = flag;
  38.                   k++;
  39.                  m = j;
  40.             }
  41.         }
  42.  
  43.     for (i = 3; i >=1; i--)
  44.     {
  45.         for(j = m-1; j <= m+2; j++)
  46.         {
  47.              if(i==3)
  48.             {
  49.                 flag = min(dp[i][j],dp[i][j+1],dp[i][j+2]);
  50.             }
  51.             else flag = min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]);
  52.         }
  53.         best_path[k] = flag;
  54.         k++;
  55.     }
  56.  
  57.     printf("\n\n");
  58.     for (i = 0; i <5; i++)
  59.     {
  60.         for (j = 0; j <6; j++)
  61.         {
  62.             printf("%d ", arr[i][j]);
  63.         }
  64.         printf("\n");
  65.     }
  66.     printf("\n\n");
  67.     for (i = 0; i <5; i++)
  68.     {
  69.         for (j = 0; j <7; j++)
  70.         {
  71.             //if(dp[i][j].length )
  72.             printf("%d ", dp[i][j]);
  73.         }
  74.         printf("\n");
  75.     }
  76.  
  77.     printf("\n\n");
  78.     for(k=0;k<5;k++)
  79.         printf("%d ", best_path[k]);
  80.  
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement