Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- int min(int a, int b,int c)
- {
- int x = a<b ? a : b;
- return x < c ? x : c;
- }
- int dp[5][7], best_path[5];
- int main()
- {
- 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 } };
- int i,j,k=0,m,n;
- for (i = 0; i <5; i++)
- {
- dp[i][0] = 9999;
- dp[i][6] = 9999;
- }
- //================
- for (i = 1; i <5; i++)
- {
- for (j = 1; j <6; j++)
- {
- dp[i][j] = arr[i][j] + min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]);
- }
- }
- int flag=99999;
- for(j = 1; j <6; j++)
- {
- if(dp[4][j]<flag)
- {
- flag = dp[4][j];
- best_path[k] = flag;
- k++;
- m = j;
- }
- }
- for (i = 3; i >=1; i--)
- {
- for(j = m-1; j <= m+2; j++)
- {
- if(i==3)
- {
- flag = min(dp[i][j],dp[i][j+1],dp[i][j+2]);
- }
- else flag = min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]);
- }
- best_path[k] = flag;
- k++;
- }
- printf("\n\n");
- for (i = 0; i <5; i++)
- {
- for (j = 0; j <6; j++)
- {
- printf("%d ", arr[i][j]);
- }
- printf("\n");
- }
- printf("\n\n");
- for (i = 0; i <5; i++)
- {
- for (j = 0; j <7; j++)
- {
- //if(dp[i][j].length )
- printf("%d ", dp[i][j]);
- }
- printf("\n");
- }
- printf("\n\n");
- for(k=0;k<5;k++)
- printf("%d ", best_path[k]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement