Advertisement
Guest User

ApplePath_có truy vết

a guest
Feb 20th, 2019
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.79 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <conio.h>
  4.  
  5. #define M 5
  6. #define N 5
  7.  
  8. int tao[M+1][N+1];
  9. int soTaoToiUu[M+1][N+1];
  10. int path[M+1][N+1];
  11.  
  12. void sinhMang()
  13. {
  14.     for (int i = 1; i <= M; i++)
  15.         for (int j = 1; j <= N; j++)
  16.         {
  17.             tao[i][j] = rand() % 10;
  18.         }
  19. }
  20.  
  21. void xuatMang()
  22. {
  23.  
  24.     for (int i = 1; i <= M; i++)
  25.     {
  26.         for (int j = 1; j <= N; j++)
  27.         {
  28.             printf("%d ", tao[i][j]);
  29.         }
  30.         printf("\n");
  31.     }
  32.  
  33.  
  34.     printf("\n\n");
  35.  
  36.     for (int i = 1; i <= M; i++)
  37.     {
  38.         for (int j = 1; j <= N; j++)
  39.         {
  40.             printf("%d ", path[i][j]);
  41.         }
  42.         printf("\n");
  43.     }
  44. }
  45.  
  46. int max(int m, int n)
  47. {
  48.     if (m > n) return m;
  49.     return n;
  50. }
  51.  
  52. int findPath(int x, int y)
  53. {
  54.     //xuatMang();
  55.     if (soTaoToiUu[x][y] != 0) return soTaoToiUu[x][y];
  56.     if (x==1 && y==1)
  57.     {
  58.         soTaoToiUu[1][1] = tao[1][1];
  59.         return tao[1][1];
  60.     }
  61.     if (x==1 && y!=1)
  62.     {
  63.         soTaoToiUu[x][y] = tao[x][y] + findPath(x, y-1);
  64.         return soTaoToiUu[x][y];
  65.     }
  66.     if (x!=1 && y==1)
  67.     {
  68.         soTaoToiUu[x][y] = tao[x][y] + findPath(x - 1, y);
  69.         return soTaoToiUu[x][y];
  70.     }
  71.     soTaoToiUu[x][y] = max(tao[x][y] + findPath(x, y-1), tao[x][y] + findPath(x-1, y));
  72.     return soTaoToiUu[x][y];
  73. }
  74.  
  75.  
  76. void truyVet(int x, int y)
  77. {
  78.     path[1][1] = 1;
  79.     while (x != 1 && y != 1)
  80.     {
  81.         path[x][y] = 1;
  82.         if (x==1 && y!=1) y--;
  83.         if (x!=1 && y==1) x--;
  84.         if (x!= 1 && y!= 1)
  85.         {
  86.             if (soTaoToiUu[x][y-1] > soTaoToiUu[x-1][y]) y--;
  87.             else x--;
  88.         }
  89.     }
  90. }
  91.  
  92. int main()
  93. {
  94.     sinhMang();
  95.     printf("%d\n", findPath(M, N));
  96.     truyVet(M,N);
  97.     xuatMang();
  98.  
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement