Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <conio.h>
- #define M 5
- #define N 5
- int tao[M+1][N+1];
- int soTaoToiUu[M+1][N+1];
- int path[M+1][N+1];
- void sinhMang()
- {
- for (int i = 1; i <= M; i++)
- for (int j = 1; j <= N; j++)
- {
- tao[i][j] = rand() % 10;
- }
- }
- void xuatMang()
- {
- for (int i = 1; i <= M; i++)
- {
- for (int j = 1; j <= N; j++)
- {
- printf("%d ", tao[i][j]);
- }
- printf("\n");
- }
- printf("\n\n");
- for (int i = 1; i <= M; i++)
- {
- for (int j = 1; j <= N; j++)
- {
- printf("%d ", path[i][j]);
- }
- printf("\n");
- }
- }
- int max(int m, int n)
- {
- if (m > n) return m;
- return n;
- }
- int findPath(int x, int y)
- {
- //xuatMang();
- if (soTaoToiUu[x][y] != 0) return soTaoToiUu[x][y];
- if (x==1 && y==1)
- {
- soTaoToiUu[1][1] = tao[1][1];
- return tao[1][1];
- }
- if (x==1 && y!=1)
- {
- soTaoToiUu[x][y] = tao[x][y] + findPath(x, y-1);
- return soTaoToiUu[x][y];
- }
- if (x!=1 && y==1)
- {
- soTaoToiUu[x][y] = tao[x][y] + findPath(x - 1, y);
- return soTaoToiUu[x][y];
- }
- soTaoToiUu[x][y] = max(tao[x][y] + findPath(x, y-1), tao[x][y] + findPath(x-1, y));
- return soTaoToiUu[x][y];
- }
- void truyVet(int x, int y)
- {
- path[1][1] = 1;
- while (x != 1 && y != 1)
- {
- path[x][y] = 1;
- if (x==1 && y!=1) y--;
- if (x!=1 && y==1) x--;
- if (x!= 1 && y!= 1)
- {
- if (soTaoToiUu[x][y-1] > soTaoToiUu[x-1][y]) y--;
- else x--;
- }
- }
- }
- int main()
- {
- sinhMang();
- printf("%d\n", findPath(M, N));
- truyVet(M,N);
- xuatMang();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement